Prove that the graphs $G$ and $H$ are not isomorphic

692 Views Asked by At

enter image description here

Let $G$ be the graph on the left and $H$ be the graph on the right.

For $G$:

number of edges: $9$

number of vertices: $6$

degree sequence: $3,3,3,3,3,3$

For $H$:

number of edges: $9$

number of vertices: $6$

degree sequence: $3,3,3,3,3,3$

I am having trouble proving these two are not isomorphic. I see $4$-cycles in $H$ but not in $G$.

1

There are 1 best solutions below

0
On

It's pretty easy to see they are in fact isomorphic. Each is the complete bipartite graph on two sets of three vertices each: the sets being the upper and lower vertices on the left, and sets of every other vertex on the ones arranged on a hexagon.