[Math] Creating a Bijection to check if Graphs are Isomorphic

graph theorygraph-isomorphism

To prove that two graphs are isomorphic I was taught to first consider the bijection between the two graphs. I was never taught however the rules when coming up with the bijection.
Is my only rule, when coming up with a bijection between two graphs, that the vertices that I match, that they must have the same degree?
eg. if a in graph 1 has a degree of 3 then I can only match it up with other vertices in graph 2 that have degrees of 3?

I am really confused on how to do this.

Best Answer

Matching up vertices with the same degree is a good start, but there will still be some (perhaps lots) of trial and error involved. Another good thing to do, once you know some of the correspondences, is to consider unknown matches adjacent to those you already know.

Here is an example which I hope will clarify the above. Please draw the following graphs (I am no good at drawing diagrams online).

  • Graph $G$: a pentagon $abcde$, including all five edges $ab,\,bc,\,cd,\,de,\,ea$, and an extra edge $ac$.
  • Graph $H$: a square $pqrs$ with edges $pq,\,qr,\,rs,\,sp$, and a vertex $t$ in the middle of the square, with edges $pt$ and $st$.

By considering degrees you could match up vertices as follows: $$\matrix{a&b&c&d&e\cr p&t&s&q&r\cr}$$ This is a bijection, but it is not an isomorphism, because $c$ and $d$ are adjacent in $G$ but the corresponding vertices $s$ and $q$ are not adjacent in $H$. So let's take it a bit more slowly.

From degrees, we see that $a$ and $c$ must match $p$ and $s$. Which is which? - perhaps you can see a reason why it doesn't matter, if not then let's just pick one of the options and try it: $$\matrix{a&b&c&d&e\cr p&?&s&?&?\cr}$$ Now $b$ is adjacent to both $a$ and $c$, so it must match a vertex adjacent to both $p$ and $s$. The only such vertex is $t$. So now we have $$\matrix{a&b&c&d&e\cr p&t&s&?&?\cr}$$ Finally, $d$ is adjacent to $c$ and $e$ is adjacent to $a$, so the only option remaining is $$\matrix{a&b&c&d&e\cr p&t&s&r&q\cr}$$ One more point: this does not quite complete the problem since we need to check all adjacencies and non-adjacencies, but we have only checked a few of them. So we could say

  • $a$ is adjacent to $b,c,e$ and no others, so $p$ should be adjacent to $t,s,q$ and no others - check - correct.
  • and the same for $b,c,d,e$.

This might look like a lot of work - unfortunately, it is a lot of work. However you may be able to redraw the graph $H$ in order to see at a glance that it "looks exactly like" $G$.

Hope this helps.

Related Question