3
$\begingroup$

enter image description here

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:

enter image description here


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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Carsten S Dec 10 '13 at 12:11
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.