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.
2026-03-27 01:43:39.1774575819
On
On
Graph isomorphism when all vertices have the same degree
4.8k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
3
There are 3 best solutions below
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).
One of them has a three cycle. They are both cubic graphs.