Are these 2 graphs isomorphic? Question regarding the placement of subgraphs

Question

So im having trouble figuring out the answer in this problem. Everything seems ok (same number of vertices, degrees etc) but i would guess that they are NOT isomorphic because in the second graph there is path of length 2 between the 2 paths of length 1, while in the first this isnt the case

Is this assumption correct?

Heres the 2 graphs in question

Answer 1

The graphs are not isomorphic, but not for the reason that you gave: there are $9$ paths of length $1$ in each graph, so the $2$ paths of length $1$ is not actually meaningful.

Here are several ways to show that they are not isomorphic.

• The graph on the left has a path of length $6$ (and in fact it has two of them); the graph on the right has no path of length greater than $5$.
• The graph on the left has only one vertex, $v_5$, that is adjacent to two vertices of degree $1$; the graph on the right has two, $v_2$ and $v_5$.
• Every vertex of degree $3$ in the graph on the left is adjacent to at least one vertex of degree $1$; the graph on the right has a vertex of degree $3$, $v_3$, that is not adjacent to any vertex of degree $1$.
• The graph on the left has two vertices of degree $1$, $v_1$ and $v_7$, with a path of length $3$ between them; the graph on the right has no such pair of vertices. (All of the distances between vertices of degree $1$ in the graph on the right are $2,4$, or $5$.)