 Graph Theory: Planar Graph & Subgraph and Spanning & Induced Graph

### Graph Theory

Graph Theory is a branch of mathematics that studies graphs. Graphs are abstractions of a social network, the connections between people and events, the connections between pages on a website, or any other kind of connection.

### Planar Graph

A graph is defined as a planar graph if it can be drawn in a plane and no edges intersect each other.

In other words, Planar graph edges intersect only at their endpoints. It can be drawn in such a way that no edges cross each other. #### Regions of Plane

The representation of planar graphs is divided into connected parts/regions that are known as Regions of the Plane. #### Degree of Region

• Degree of Interior region = Number of edges enclosing that region
• Degree of Exterior region = Number of edges exposed to that region

Here, this planar graph splits the plane into 3 regions- R1, R2, and R3 where-

Degree (R1) = 3

Degree (R2) = 3

Degree (R3) = 4

#### Planar Graph Chromatic Number

The Chromatic Number of any planar graph is always less than or equal to 4. Thus, any planar graph always requires a maximum of 4 colors for coloring its vertices.

#### Planar Graph Properties

Property 1: The sum of all the degrees of the vertices is twice the number of edges in the graph. Property 2: The sum of all the degrees of the regions is twice the number of edges in the graph. Property 3: If G is a Planar graph with ‘e’ edges, ‘v’ vertices and ‘r’ number of regions in the planar representation of G, then-

r = e – v + 2

This is called Euler’s Formula and remains the same in all the planar representations of the graph.

Property 4: If G is a planar graph with k components, then-

r = e – v + (k + 1)

Property 5: If a connected planar graph G has e edges and v vertices, then 3v-e≥6.

Example: Prove that complete graph K4 is planar.

The complete graph K4 contains 4 vertices and 6 edges.

We know that for a connected planar graph 3v-e≥6.Hence for K4, we have 3×4-6=6 which satisfies the property (3).

Thus K4 is a planar graph. Hence Proved.

Property 6: A complete graph Kn is a planar if and only if n<5.

Property 7: A complete bipartite graph Kmn is planar if and only if m<3 or n>3.

#### Non-planar Graph

A graph is defined as a non-planar graph if it can be drawn in a plane with edges that intersect each other.

In other words, It can be drawn in such a way that edges should cross each other. Example: Show that K5 is non-planar.

The complete graph K5 contains 5 vertices and 10 edges.

Now, for a connected planar graph 3v-e≥6.

Hence, for K5, we have 3 x 5-10=5 (which does not satisfy property 3 because it must be greater than or equal to 6).

Thus, K5 is a non-planar graph.

### Applications of Graph Coloring

Some applications of graph coloring include:

• Register Allocation
• Map Coloring
• Bipartite Graph Checking
• Making a time table, etc.

### Handshaking Theorem

The sum of degrees of all the vertices in a graph G is equal to twice the number of edges in the graph.

Mathematically it can be stated as:

∑v∈Vdeg(v)=2e

Proof: Let G = (V, E) be a graph where V = {v1,v2, . . . . . . . . . .} be the set of vertices and E = {e1,e2 . . . . . . . . . .} be the set of edges. We know that every edge lies between two vertices so it provides degree one to each vertex. Hence each edge contributes degree two for the graph. So the sum of degrees of all vertices is equal to twice the number of edges in G.

Hence,         ∑v∈Vdeg(v)=2e

### Subgraph

A graph G’ is said to be a subgraph if it is extracted from graph G where the set of vertices and edges are subsets of graph G.

In other words, if all the vertices and edges of a graph G’ belong to G, and each edge of G’ has the same end vertices in G’ as in G. Original Subgraph A graph by deleting the edge between V4 and V5. A graph by deleting the edge between V4 and V5. A graph by deleting the edge between V2 and V3. A graph by deleting the edge from V2 to V4.

Case 1: In any planar graph, if degree of each region is K, then-

K x |R| = 2 x |E|

Case 2: In any planar graph, if degree of each region is at least K (>=K), then-

K x |R| <= 2 x |E|

Case 3: In any planar graph, if degree of each region is at most K (<=K), then-

K x |R| >= 2 x |E|

Points to remember:

• Vertex and edge sets are subsets of those of G
• a supergraph of a graph G is a graph that contains G as a subgraph.
• A graph G contains another graph H if some subgraph of G
• is H or
• is isomorphic to H.
• H is a proper subgraph if H!=G

### Spanning Tree

In graph theory, a spanning tree is a subgraph that is a tree which includes all of the vertices of G. If a vertex is missed, then it is not a spanning tree.

In other words, a spanning tree is a subgraph of G, which includes all the vertices of G with (n-1) edges. Where ‘n’ is no. of vertices. All the possible created spanning trees from the original graph would have the same no. of vertices but the no. of edges would be (n-1). Original Spanning tree

The total number of spanning trees with n vertices that can be created from a complete graph is equal to n power (n-2).

If we have n = 5, the maximum number of possible spanning trees is equal to 5 power (5-2) = 125. Thus, 125 spanning trees can be formed from a complete graph with 5 vertices. Fig – Spanning tree 1 Fig – Spanning tree 2 Fig – Spanning tree 3

Points to remember:

• Subgraph H has the same vertex set as G
• Possibly not all the edges
• “H spans G”

Theorem: A graph is connected if and only if it has a spanning tree.

Proof: Let G be a connected graph. Delete edges from G that are not bridges until we get a connected subgraph H in which each edge is a bridge. Then H is a spanning tree. On the other hand, if there is a spanning tree in G, there is a path between any pair of vertices in G; thus G is connected.

#### Applications of the Spanning Tree

Basically, a spanning tree is used to find a minimum path to connect all nodes of the graph. Some of the common applications of the spanning tree are listed as follows –

• Cluster Analysis
• Civil network planning
• Computer network routing protocol

#### Properties of Spanning Tree

• There can be more than one spanning tree of a connected graph G.
• A spanning tree has n-1 edges, where ‘n’ is the number of nodes.
• There can be a maximum n power (n-2) number of spanning trees that can be created from a complete graph.
• A spanning tree does not have any cycles or loop.
• A spanning tree is connected with least no. of edges, so removing one edge from the tree will make the graph disconnected.
• A spanning tree is maximally acyclic, so adding one edge to the tree will create a loop.
• If the graph is a complete graph, then the spanning tree can be constructed by removing maximum (e-n+1) edges, where ‘e’ is the number of edges and ‘n’ is the number of vertices.

So, a spanning tree is a subset of connected graph G, and there is no spanning tree of a disconnected graph.

#### Minimum Spanning Tree

A graph is said to be a minimum spanning tree, if the sum of all the weights of the edges is minimum. The weight of the spanning tree is the distance assigned to each edge connected to the vertices. Original Minimum Spanning tree As per the statement, Fig – 2 has the lowest sum of all the edges weight among all the Minimum Spanning tree, therefore Fig – 2 is the Minimum Spanning tree.

#### Applications of Minimum Spanning Tree

The applications of the minimum spanning tree are given as follows –

• Minimum spanning trees can be used to design water-supply networks, telecommunication networks, and electrical grids.
• Majorly, spanning trees are used to find paths in the map.

#### Algorithms for Minimum Spanning Tree

A minimum spanning tree can be found from a weighted graph by using the algorithms given below –

• Prim’s Algorithm
• Kruskal’s Algorithm

#### Prim’s algorithm

It is a greedy algorithm that starts with an empty spanning tree. It is used to find the minimum spanning tree from the graph. This algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.

#### Kruskal’s algorithm

This algorithm is also used to find the minimum spanning tree for a connected weighted graph. Kruskal’s algorithm also follows a greedy approach, which finds an optimum solution at every stage instead of focusing on a global optimum.

Note: Later, in upcoming lesson, you will learn in detail about Prim’s & Kruskal’s algorithm,

### Vertex Induced Graph

An induced subgraph formed from some of the vertices and all the edges (from the original graph) connecting pairs of vertices in the original graph. Original Vertex Induced Graph ### Edge Induced Graph

An induced subgraph formed from some of the edges (from the original graph) and the vertices that are at their endpoints. Original Edge Induced Graph If you find anything incorrect in the above-discussed topic and have further questions, please comment below.

Connect on: