1
$\begingroup$

Are these graphs homeomorphic?

a)

enter image description here

and the Peterson graph?

b)

enter image description here

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?

$\endgroup$
4
  • 1
    $\begingroup$ Do you mean isomorphic? $\endgroup$
    – James
    Oct 10, 2014 at 15:24
  • $\begingroup$ Homeomorphic is a topological notion, and isomorphic is an algebraic notion, I was wondering which you meant. $\endgroup$
    – James
    Oct 10, 2014 at 15:27
  • 1
    $\begingroup$ Homeomorphism is a concept in graph theory as well. $\endgroup$
    – John Smith
    Oct 10, 2014 at 15:31
  • 1
    $\begingroup$ Some authors use "graph homeomorphism" to mean the same thing as "graph isomorphism". However the Wikipedia article Graph homeomorphism defines it to be a more general relation, namely graphs $G$ and $G'$ are homeomorphic iff subdivisions of $G$ and $G'$ may be found which are isomorphic. [A subdivision of a (simple undirected) graph inserts new nodes on edges.] $\endgroup$
    – hardmath
    Oct 10, 2014 at 16:05

1 Answer 1

1
$\begingroup$

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.)

$\endgroup$
3
  • 1
    $\begingroup$ :In my book it says that two graphs are homeomorphic if and only if each can be obtained from the same graph by adding vertices (necessarily of degree 2) to edges $\endgroup$
    – clarkson
    Oct 10, 2014 at 17:32
  • 1
    $\begingroup$ Okay,that is the more general relation. If two graphs are isomorphic, then they are also homeomorphic (no need to "subdivide" edges), but the converse isn't true. Since subdividing can introduce as many degree 2 vertices as we wish, the criterion of reduced degree sequences equal is necessary but not sufficient for graph homeomorphism. $\endgroup$
    – hardmath
    Oct 10, 2014 at 18:48
  • 1
    $\begingroup$ I think a better way to express graph homeomorphism of $G$ and $G'$ is to say they may be made isomorphic by a series of graph subdivisions (rather than saying each may be obtained from the same graph by the process of subdividing edges). $\endgroup$
    – hardmath
    Oct 10, 2014 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.