Are these graphs homeomorphic?
a)
and the Peterson graph?
b)
I think both are not homeomorphic.Is it correct?Is there a way I can show that they are not homemorphic
Also two graphs being isomorphic doesn't imply they are homeomorphic right?
[Math] homeomorphic graphs
discrete mathematicsgraph theory
Best Answer
If by graph homeomorphisms we mean the isomorphisms of graph subdivisions (isomorphism after introducing new nodes that subdivide one or more edges), then a necessary (but not always sufficient) criterion asks if the reduced degree sequences of the two graphs (meaning that degree $2$ entries are deleted from the degree sequences) are the same.
(a) is not (isomorphic to) the Peterson graph because it has a vertex of degree four and the Peterson graph is cubic (all vertices are degree 3). The reduced degree sequences are thus different, and thus the graphs are not homeomorphic.
(b) and (c) appear isomorphic to me, and thus homeomorphic in the more general sense. Each has a single vertex of degree two and the rest of degree three. Printing out the graphs and labelling the vertices that correspond (starting with the single vertex of degree two and working outward through its neighbors) should quickly prove the point, one way or the other. (I carried out this exercise and succeeded in labelling the graphs correspondingly.)