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.
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.