Are there simple graphs $G$ and $H$ both with vertex degrees $2,2,2,2,3,3$ such that $G$ and $H$ are NOT isomorphic? if so, draw them, otherwise, explain why they don't exist.
I'm having trouble answering this question. I know that this sequence is graphical, but how can I know how many are there that are not isomorphic and how to draw them. Can someone please help?
Thank you!
Best Answer
Yes, there are. I'll describe two such graphs.
First, arrange the six vertices in a 2 by 3 grid. Then connect vertices so as to form the number $8$ as seen on sports scoreboards or some digital clocks. This is what a commenter refers to as a theta graph.
For the second example, call the vertices of degree $3$ $A$ and $B$ and the other four $x,y,z,w$. Set $A$ adjacent to $x,y,z$, $B$ adjacent to $x,y,w$, and $z$ adjacent to $w$.
In the first example, the degree $3$ vertices are adjacent but in the second they are not, so the two graphs are non-isomorphic.