Graph isomorphism

Graph $G_{1}$ and $G_{2}$ are isomorphism if there exists a bijection $f : V_{1} \to V_{2}$ such that $(u, v) \in E_{1}$ if and only if $(f (u), f (v)) \in E_{2}$ .
- The bijection $f$ is called the isomorphism from $G_{1}$ to $G_{2}$
- Notation: $G_{2} = f (G_{1})$
There are $n!$ possible bijections
Graph invariant:
- Have same number of edges and vertices
- Same degree of vertices
- Same cycle structure

Prove that two graph are not isomorphic
Proof:
- Consider, a prover $P$ and a verifier $V$
- Input: $G_{0} = (V = {1, ..., n}, E_{0})$ and $G_{1} = (V = {1, ..., n}, E_{1})$ allegedly not isomorphic
- Step 1: $V$ picks a random permutation/bijection 𝜋: {1, … , 𝑛} → {1, … , 𝑛}, a random bit 𝑏 ∈ {0,1}, and send $H = π (G_{b})$ to $P$
- Step 2: $P$ checks if $H$ is isomorphic to $G_{0}$ or $G_{1}$ (in polynomial time) and send $b^{'} = 0$ or $b^{'} = 1$ to $V$ , respectively
- Step 3: $V$ accepts (that the graph are non-isomorphic) is and only if $b^{'} = b$
Completeness: ?
- If the graphs are not isomorphic, then 𝐻 is isomorphic to 𝐺! , but not to the other input graph 𝐺”#! . This allows P to determine 𝑏′ = 𝑏 every time
Soundness:
- If the graphs are isomorphic, then 𝐻 is isomorphic to both 𝐺$ and 𝐺” . Therefore, it is impossible to tell from which input graph is used by V. With probability 1/2, we have 𝑏≠ 𝑏 and the verifier rejects

StrixTheKiet Notes