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.
