Graph Theory - Isomorphism

Isomorphic Graphs

Two graphs G₁ and G₂ are said to be isomorphic if −

Their number of components (vertices and edges) are same.
Their edge connectivity is retained.

Note − In short, out of the two isomorphic graphs, one is a tweaked version of the other. An unlabelled graph also can be thought of as an isomorphic graph.

There exists a function ‘f’ from vertices of G₁ to vertices of G₂
   [f: V(G₁) ⇒ V(G₂)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G₁, then the
edge {f(U), f(V)} ∈ G₂, then G₁ ≡ G₂.

Note

If G₁ ≡ G₂ then −

|V(G₁)| = |V(G₂)|

|E(G₁)| = |E(G₂)|

Degree sequences of G₁ and G₂ are same.

If the vertices {V₁, V₂, .. Vk} form a cycle of length K in G₁, then the vertices {f(V₁), f(V₂),… f(Vk)} should form a cycle of length K in G₂.

All the above conditions are necessary for the graphs G₁ and G₂ to be isomorphic, but not sufficient to prove that the graphs are isomorphic.

(G₁ ≡ G₂) if and only if (G₁− ≡ G₂−) where G₁ and G₂ are simple graphs.
(G₁ ≡ G₂) if the adjacency matrices of G₁ and G₂ are same.
(G₁ ≡ G₂) if and only if the corresponding subgraphs of G₁ and G₂ (obtained by deleting some vertices in G1 and their images in graph G₂) are isomorphic.

Example

Which of the following graphs are isomorphic?

In the graph G₃, vertex ‘w’ has only degree 3, whereas all the other graph vertices has degree 2. Hence G3 not isomorphic to G₁ or G₂.

Taking complements of G₁ and G₂, you have −

Here, (G₁− ≡ G₂−), hence (G₁ ≡ G₂).

Planar Graphs

A graph ‘G’ is said to be planar if it can be drawn on a plane or a sphere so that no two edges cross each other at a non-vertex point.

Example

Regions

Every planar graph divides the plane into connected areas called regions.

Example

Degree of a bounded region r = deg(r) = Number of edges enclosing the regions r.

deg(1) = 3
deg(2) = 4
deg(3) = 4

deg(4) = 3
deg(5) = 8

Degree of an unbounded region r = deg(r) = Number of edges enclosing the regions r.

deg(R₁) = 4
deg(R₂) = 6

In planar graphs, the following properties hold good −

In a planar graph with ‘n’ vertices, sum of degrees of all the vertices is −

n Σ i=1 deg(V_i) = 2|E|

According to Sum of Degrees of Regions/ Theorem, in a planar graph with ‘n’ regions, Sum of degrees of regions is −

n Σ i=1 deg(ri) = 2|E|

Based on the above theorem, you can draw the following conclusions −

In a planar graph,

If degree of each region is K, then the sum of degrees of regions is −

K|R| = 2|E|

If the degree of each region is at least K(≥ K), then

K|R| ≤ 2|E|

If the degree of each region is at most K(≤ K), then

K|R| ≥ 2|E|

Note − Assume that all the regions have same degree.

According to Euler’s Formulae on planar graphs,

If a graph ‘G’ is a connected planar, then

|V| + |R| = |E| + 2

If a planar graph with ‘K’ components, then

|V| + |R|=|E| + (K+1)

Where, |V| is the number of vertices, |E| is the number of edges, and |R| is the number of regions.

Edge Vertex Inequality

If ‘G’ is a connected planar graph with degree of each region at least ‘K’ then,

|E| ≤ k / (k-2) {|v| - 2}

You know, |V| + |R| = |E| + 2

K.|R| ≤ 2|E|

K(|E| - |V| + 2) ≤ 2|E|

(K - 2)|E| ≤ K(|V| - 2)

|E| ≤ k / (k-2) {|v| - 2}

If ‘G’ is a simple connected planar graph, then

|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4

There exists at least one vertex V •∈ G, such that deg(V) ≤ 5.

If ‘G’ is a simple connected planar graph (with at least 2 edges) and no triangles, then

|E| ≤ {2|V| – 4}

Kuratowski’s Theorem

A graph ‘G’ is non-planar if and only if ‘G’ has a subgraph which is homeomorphic to K₅ or K_3,3.

Homomorphism

Two graphs G₁ and G₂ are said to be homomorphic, if each of these graphs can be obtained from the same graph ‘G’ by dividing some edges of G with more vertices. Take a look at the following example −

Divide the edge ‘rs’ into two edges by adding one vertex.

The graphs shown below are homomorphic to the first graph.

If G₁ is isomorphic to G₂, then G is homeomorphic to G2 but the converse need not be true.

Any graph with 4 or less vertices is planar.
Any graph with 8 or less edges is planar.
A complete graph K_n is planar if and only if n ≤ 4.
The complete bipartite graph K_{m, n} is planar if and only if m ≤ 2 or n ≤ 2.
A simple non-planar graph with minimum number of vertices is the complete graph K₅.
The simple non-planar graph with minimum number of edges is K_{3, 3}.

Polyhedral graph

A simple connected planar graph is called a polyhedral graph if the degree of each vertex is ≥ 3, i.e., deg(V) ≥ 3 ∀ V ∈ G.

3|V| ≤ 2|E|
3|R| ≤ 2|E|

Previous Page Print Page