# To Obtain G2 from G1, we can use this elementary subdivisions

 Page 2/9 Date 20.07.2021 Size 249.09 Kb.

## To Obtain G2 from G1, we can use this elementary subdivisions:

• Remove the edge {a , c}, add the vertex f, and add the edges {a , f} and {f , c}
• Remove the edge {b , c}, add the vertex g, and add the edges {b , g} and {g , c}
• Remove the edge {b , g}, add the vertex h, and add the edges {b , h} and {h , g}

## Illustration:

f

G

a

b

c

d

e

g

h

i

j

g

H

a

f

e

d

i

j

c

h

h

d

K3,3

f

e

j

i
• Graph G is the Petersen Graph.
• H is a subgraph of G obtained by removing vertex b and edges {b , g},{b , a} and {b , c}.
• Subgraph H is Homeomorphic to K3,3.
• Hence, G is nonplanar.

a

b

H

c

d

e

f

g

i

a

b

K5

c

g

i
• Here graph G is an Undirected Graph with the given vertices and edges.
• H is a subgraph of G obtained by deleting h, j, and k and edges { i, g }, { g, c }, { c, c }.
• Subgraph H is homeomorphic to k5 .
• Hence graph G is nonplanar.

a

b

h

G

c

d

e

f

g

k

i

j