Graph isomorphism when all vertices have the same degree

4.8k Views Asked by At

Are 2 connected graphs isomorphic if they have the same number of vertices and each vertex has the same degree $k$? I don't know how to prove it but I also can't find a counter example.

3

There are 3 best solutions below

3
On BEST ANSWER

enter image description here

One of them has a three cycle. They are both cubic graphs.

2
On

Let $k=2$. Graph 1: two triangles. Graph 2: a hexagon.

(OP inserted connected after this answer was posted. The answer is still no.)

1
On

Start with the cube graph. Add a diagonal to the top face; this increases the degree of two vertices to become $4$. From these vertices, remove the downward edges; this decreases the degree of two bottom vertices. Join these by a face diagonal. This new graph has eight vertices of degree $3$ (like the cube), but has several $3$-cycles (unlike the cube).