Determining if two graphs are isomorphic I'm supposed to determine if the above graphs are isomorphic. I thought there was because there was a bijection from the set of vertices of graph G to the set of vertices of graph H, and because adjacency as preserved. However, this was my book's explanation as to why it was NOT isomorphic: I understand that since a has a degree of 2, it can only correspond to either t, u, x, or y. However, I don't understand why the fact that those vertices in H are adjacent to other vertices of degree two makes the graphs not isomorphic. The book didn't say anything further than that, so I guess it should be self-evident and obvious, but I really don't understand what that has to do with anything. Can somebody explain this?

• Maybe you have the wrong idea about what isomorphism means. You seem to claim that there is an adjacency preserving bijection, can you name it? – Carsten S Dec 10 '13 at 12:11

Two graphs $G$, $H$, are isomorphic if they only differ in the names attached to vertices. Thus, any property of $G$ with doesn't include vertex names must hold in $H$ and vice versa.
In your case, there are lots of ways to argue why these two aren't isomorphic. For example, $H$ contains a circle of 4 vertices which all have degree $3$ - namely $s,w,z,v$. $G$, on the other hand, has no such circle.
There are two adjacent vertices of degree $2$ in $H$, namely $t$ and $u$. Suppose $\phi: H \rightarrow G$ is an isomorphism of graphs, then $\phi(t)$ and $\phi(u)$ are adjacent vertices of degree $2$ in $G$. But $G$ has no such vertices.