Homeomorphic Graphs

1 min read

HOMEOMORPHIC GRAPHS: Two graphs are said to be homeomorphic if and only if each can be obtained from the same graph by adding vertices (necessarily of degree 2) to edges.
The graphs G1 and G2 in Figure (2.6) are homeomorphic since both are obtainable from the graph G in that figure by adding a vertex to one of its edges.

In Figure 2.7, we show two homeomorphic graphs, each obtained from K5 by adding vertices to edges of K5 (In each case, the vertices of K5 are shown with solid dots).