Isomorphic Graphs / Homeomorphic graphs/ Planar graph

Isomorphic Graphs

Graphs G1 and G2 are isomorphic if there is a one-to-one, onto function f from the vertices of G1 to vertices of G2 and a one-to-one, onto function g from the edges of G1 to the edges of G2, so that e=(v,w) in G1 if and only if g(e)=(f(v), f(w)) in G2.

Theorem

Graphs G1 and G2 are isomorphic if and only if for some ordering of their vertices, their adjacency matrices are equal.

---

Homeomorphic graphs

Graphs G1 and G2 are homeomorphic if G1 and G2 can be reduced to isomorphic graphs by performing a sequence of series reductions

---

Planar graph

A graph is planar if it can be drawn in the plane without its edges crossing,

Theorem 1

if G is a connected planar graph, then v-e+f=2 and 2e>=sf.

v=number of vertices

e=number of edges

f=number of faces, including the exterior face

s=minimum number of edges for making a face

Theorem 2

G is a planar graph if and only if G does not contain a subgraph homeomorphic to either K5 or K3,3.

following graph is not planar: