Planar Graph

Planar Graph:

A graph is said to be planar if it can be drawn in a plane so that no edge cross.

Example: The graph shown in fig is planar graph.

Region of a Graph: Consider a planar graph G=(V,E).A region is defined to be an area of the plane that is bounded by edges and cannot be further subdivided. A planar graph divides the plans into one or more regions. One of these regions will be infinite.

Finite Region: If the area of the region is finite, then that region is called a finite region.

Infinite Region: If the area of the region is infinite, that region is called a infinite region. A planar graph has only one infinite region.

Example: Consider the graph shown in Fig. Determine the number of regions, finite regions and an infinite region.

Solution: There are five regions in the above graph, i.e. r₁,r₂,r₃,r₄,r₅.

There are four finite regions in the graph, i.e., r₂,r₃,r₄,r₅.

There is only one finite region, i.e., r₁

Properties of Planar Graphs:

1. If a connected planar graph G has e edges and r regions, then r ≤e.
2. If a connected planar graph G has e edges, v vertices, and r regions, then v-e+r=2.
3. If a connected planar graph G has e edges and v vertices, then 3v-e≥6.
4. A complete graph K_n is a planar if and only if n<5.
5. A complete bipartite graph K_mn is planar if and only if m<3 or n>3.

Example: Prove that complete graph K₄ is planar.

Solution: The complete graph K₄ contains 4 vertices and 6 edges.

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

Thus K₄ is a planar graph. Hence Proved.

Non-Planar Graph:

A graph is said to be non planar if it cannot be drawn in a plane so that no edge cross.

Example: The graphs shown in fig are non planar graphs.

These graphs cannot be drawn in a plane so that no edges cross hence they are non-planar graphs.

Properties of Non-Planar Graphs:

A graph is non-planar if and only if it contains a subgraph homeomorphic to K₅ or K_3,3

Example1: Show that K₅ is non-planar.

Solution: The complete graph K₅ contains 5 vertices and 10 edges.

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

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

Thus, K₅ is a non-planar graph.

Example2: Show that the graphs shown in fig are non-planar by finding a subgraph homeomorphic to K₅ or K_3,3.

Solution: If we remove the edges (V₁,V₄),(V₃,V₄)and (V₅,V₄) the graph G₁,becomes homeomorphic to K₅.Hence it is non-planar.

If we remove the edge V_2,V7) the graph G₂ becomes homeomorphic to K_3,3.Hence it is a non-planar.

Graph Coloring:

Suppose that G= (V,E) is a graph with no multiple edges. A vertex coloring of G is an assignment of colors to the vertices of G such that adjacent vertices have different colors. A graph G is M-Colorable if there exists a coloring of G which uses M-Colors.

Proper Coloring: A coloring is proper if any two adjacent vertices u and v have different colors otherwise it is called improper coloring.

Example: Consider the following graph and color C={r, w, b, y}.Color the graph properly using all colors or fewer colors.

The graph shown in fig is a minimum 3-colorable, hence x(G)=3

Solution: Fig shows the graph properly colored with all the four colors.

Fig shows the graph properly colored with three colors.

Chromatic number of G: The minimum number of colors needed to produce a proper coloring of a graph G is called the chromatic number of G and is denoted by x(G).

Example: The chromatic number of K_n is n.

Solution: A coloring of K_n can be constructed using n colours by assigning different colors to each vertex. No two vertices can be assigned the same colors, since every two vertices of this graph are adjacent. Hence the chromatic number of K_n=n.

Applications of Graph Coloring

Some applications of graph coloring include:

• Register Allocation
• Map Coloring
• Bipartite Graph Checking
• Mobile Radio Frequency Assignment
• Making a time table, etc.

State and prove Handshaking Theorem.

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 = {v₁,v₂, . . . . . . . . . .} be the set of vertices and E = {e₁,e₂ . . . . . . . . . .} 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