Determine which pairs of graphs below are isomorphic.

Question

I've managed to show that $A \ncong C$, since $A$ doesn't has a 4-cycle, and $C$ does.

Likewise I suspect that $B \ncong C$, but this is just by inspection.

Any other observation?

Answer 1

As you noted, $C$ has $4$-cycles, but $A$ does not, so $A,C$ are not isomorphic.

For $A,B$, consider diameters . . .

The diameter of $A$ is $2$, but the diameter of $B$ is $3$, so $A,B$ are not isomorphic.

For $B,C$, consider geodesic paths . . .

For any two vertices of $B$ which are distance $3$ from each other, there are four distinct paths of length $3$ between them.

For any two vertices of $C$ which are distance $3$ from each other, there is exactly one path of length $3$ between them.

Hence $B,C$ are not isomorphic.

For the graphs $B,C$, here's another the way to see the distance $3$ discrepancy . . .

For graph $B$, if two vertices $u,v$ are such that $d(u,v)=3$, then if $x$ is any of the $3$ neighbors of $u$, we have $d(x,v)=2$.

For graph $C$, if two vertices $u,v$ are such that $d(u,v)=3$, there is only one neighbor $x$ of $u$ such that $d(x,v)=2$.

Answer 2

Graph $A$ is the Petersen graph, whose automorphism group is $S_5$. It does not contain a 10-cycle (I mean the automorphism group: there is no element of order $10$ in $S_5$). But $B$ is a regular $10$-gon with all the long diagonals. Its automorphism group clearly contains a $10$-cycle (it is in fact isomorphic to $D_{10}$).

Maybe it is worth computing the automorphism group of $C$ with the orbit stabilizer theorem...