7-10. Graph isomorphism

Graph isomorphism

Isomorphic

Graphs $G$ and $H$ are isomorphic if there is an isomorphism between them: A function $f$ from the vertices of $G$ to the vertices of $H$ such that:

• $f$ is a bijection (function)

• $f$ takes edges to edges:

  For all vertices $x,y$ in $G$, if	Edges-to-edges (1) graph G {node[shape=point];x[xlabel="x"];y[xlabel="y"];y--x} Link to original	then	Edges-to-edges (2) graph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"];y--x} Link to original	in $H$.

• $f$ takes non-edges to non-edges:

  For all vertices $x,y$ in $G$, if	Non-edges-to-non-edges (1) graph G {node[shape=point];x[xlabel="x"];y[xlabel="y"]} Link to original	then	Non-edges-to-non-edges (2) graph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"]} Link to original	in $H$.

Link to original

title: Example
 
![](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%206.%20Graphs/Diagrams/Pasted%20image%2020211103154548.png)
 
The function $f$ defined by taking
 
$$
	f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E
$$
 
is an isomorphism, showing that graphs $G$ and $H$ are isomorphic.

Isomorphic or not?

We need to determine whether two graphs, say $G$ and $H$ are isomorphic or not.

$$\begin{array}{rl}\text{isomorphic}& =\text{there is an isomorphism}\\ \text{not isomorphic}& =\text{there is no isomorphism}\end{array}$$

• We can try all possible functions from $G$ to $H$, and check whether any of them is an isomorphism.
• But this might take a lot of time: there are $4^5=1024$ possible functions even for this example.

Invariants

Invariant

A property $\mathcal{P}$ of graphs is called an invariant if ==it is ‘preserved under isomorphisms’: If $G$ and $H$ are isomorphic graphs, and $G$ has property $\mathcal{P}$, then $H$ has property $\mathcal{P}$ as well==.

Link to original

title: Example 1: "Having $5$ vertices" is an invariant
If $G$ and $H$ are isomorphic graphs, and $G$ has $5$ vertices, then $H$ has $5$ vertices too.
 
This is because, if $G$ and $H$ are isomorphic, then there is an isomorphism $f$ between them.
 
- $f$ is a [[Bijection (function)|bijection (function)]] from the vertices of $G$ (domain) to the vertices of $H$ (codomain).
  ![[Bijection f between graphs]]
- As $f$ is one-to-one, $H$ has at least $5$ vertices.
- As $f$ is onto, $H$ has at most $5$ vertices.

title: Example 2: Determine whether $G$ and $H$ are isomorphic or not
 
We've just seen that the property "having $5$ vertices" is an invariant.
This property holds for $G$, but not for $H$. Therefore, $G$ and $H$ are not isomorphic.
 
```graphviz
graph G {
	label=G
	e--d,a
	d--a,c
	b--a,c
}
 
graph H {
	label=H
	w--z,x
	y--x,z
}

title: Example 3: Determine whether $G$ and $G'$ are isomorphic or not
 
In this case, we say "having a vertex of degree $3$" is an **invariant**.
 
This property holds in $G$ (e.g. $\text{degree}(a) = 3$), but does not hold in $G'$, showing that $G$ and $G'$ are not isomorphic.
 
```graphviz
graph G {
	label=G
	b--a,c
	d--a,c,e,f
	c--e
	a--e
	c--f
}
 
graph H {
	label="G'"
	g--h,i,k,j
	k--i,j,l
	j--l,i
	i--h
}

title: Example 4: Determine whether $G$ and $G'$ are isomorphic or not
 
The function $f$ defined by taking
 
$$
	f(a) = 4, f(b) = 2, f(c) = 3, f(d) = 1, f(e) = 5
$$
 
is an isomorphism (because $f$ is a bijection, takes edges to edges and non-edges to non-edges). This shows that graphs $G$ and $H$ are isomorphic.
 
```graphviz
graph G {
	label=G
	d--e,a,b
	e--c,a
	a--c,b
}
 
graph H {
	label="H"
	1--2,4,5
	2--4
	3--4,5
	4--5
}

title: Always keep in mind that if $h$ is an isomorphism between graphs $G$ and $H$, then for every vertex $x$ in $G$, the degrees of $x$ and $h(x)$ must be the same.

How to decide?

You are given a task to determine whether two graphs $G$ and $H$ are isomorphic or not.

It is not known:

• whether the problem is solvable in polynomial time we don’t know whether there is a method to check isomorphism without trying all functions
• whether the problem is definitely NOT solvable in polynomial time for many other problems, there are known proofs

We can try to determine in parallel whether:

• We can describe a bijection between the vertices of $G$ and $HG$ that ‘takes’ edges to edges, non-edges to non-edges. If we succeed, answer is yes.
• We can find an invariant $\mathcal{P}$ and show that $G$ has $\mathcal{P}$ but $H$ doesn’t, or the other way around. If we succeed, answer is no.