# Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing an oracle that solves graph isomorphism for (n-1) vertices.

To be clear, the oracle only tells 'Yes' or 'No'. It does not give us the isomorphism.

This problem appears as an exercise in Arora-Barak's chapter on Interactive Proofs.

How do I show that Graph Isomorphism is downward self-reducible?

My attempt is to start with an arbitrary vertex in $$G_1$$ and guess its image in $$G_2$$, and remove them and make an oracle call on the remaining graph. But now, I do not know how to proceed. These graphs being isomorphic may not necessarily mean that the original graphs are isomorphic.

• I removed your "NP-complete" tag, since graph isomorphism isn't known to be NP-complete (and seems not to be -- if it were, the polynomial hierarchy would collapse). Apr 24 '19 at 13:30
• @Apass.Jack clarfied Apr 25 '19 at 19:18
• Does the "Chapter on Interactive Proofs" imply probabilistic methods? Although I believe graph isomorphism is deterministic downward self polynomial-time reducible, can you clarify that the definition in the book is indeed having nothing to do randomization or probability? I do not have the book. May 7 '19 at 4:52

This answer shows how to prove an easier variation, the case of (undirected loopless) multigraph isomorphism.

### The problem of multigraph isomorphism is downward self-reducible

The simple idea is to merge two vertices in a way that distinguish those two vertices and edges involving them.

Let $$G$$ be a multigraph. If the sum of degrees of two vertices reaches the maximum, we will call an ordered pair of those two vertices a degree-maximum pair. For a degree-maximum pair $$(u,v)$$, construct $$G_{u,v}$$ as follows.

• Its vertices are all vertices of $$G$$ except $$u$$ and $$v$$, together with a new vertex $$u_v$$ which is understood as $$u$$ merged by $$v$$. Note that $$G_{u,v}$$ has one less vertice than $$G$$.

• Its edges consists of two parts.

• the edges of $$G$$ whose endpoints are neither $$u$$ nor $$v$$ with the same multiplicity. Let $$m$$ be the maximum multiplicity of these edges.
• for all vertex $$w$$ of $$G$$ that is neither $$u$$ nor $$v$$, edge $$\{w, u_v\}$$ with multiplicity that is the sum of the multiplicity of $$\{w,u\}$$ in $$G$$ and the product of $$m+1$$ and the multiplicity of $$\{w,v\}$$ in $$G$$.

It is easy to see that if we are given a multigraph $$G'$$ that is isomorphic to $$G_{u,v}$$ for some multigraph $$G$$, we can reconstruct $$G$$ from $$G'$$ up to isomorphism.

Suppose we are given two graphs of $$n$$ vertices, $$G$$ and $$H$$. Use the oracle to compare $$G_{u,v}$$ with $$H_{x,y}$$ for all tuples $$(u,v,x,y)$$, where $$(u,v)$$ is a degree-maximum pair in $$G$$ and $$(x,y)$$ is a degree-maximum pair in $$H$$. Once the oracle return yes, we conclude $$G$$ and $$H$$ are isomorphic; otherwise the oracle always return no, in which case we conclude $$G$$ and $$H$$ are not isomorphic. It take polynomial time to construct $$G_{u,v}$$ from $$G$$ or $$H_{x,y}$$ from $$H$$. There are less than $$n^2$$ tuples. So the whole algorithm takes polynomial time. QED.

I am yet to find a proof that shows the problem of (non-multi)graph isomorphism is downward self-reducible.

• As my effort to simplify is too aggressive, there is a minor/critical flaw in my algorithm above. I should have selected a degree-minimum connected pair $(u,v)$. Apr 26 '19 at 5:00