Split graphs are GI-complete

Question

According to the Wikipedia article about the graph isomorphism problem, it's claimed that split graphs are GI-complete. Does it mean that any two (simple undirected connected) graphs $G_1, G_2$ can be transformed to two split graphs $S_1, S_2$ respectively so that $S_1\cong S_2$ iff $G_1\cong G_2$? If that's the case, how is that transformation from any graph to a split graph performed?

Answer 1

One possible transformation goes as follows. Given a graph $G$ with $n$ vertices and $m$ edges, we construct a split graph $S$ with $n+m$ vertices:

1. Begin with a clique on the same vertex set as $G$.
2. For each edge $vw \in E(G)$, create a new vertex $x_{vw}$ adjacent to $v$ and $w$ (and to no other vertices).

This is a split graph: the clique is created in step 1 and the independent set is created in step 2. Also, if we start with a graph $G$ on at least $4$ vertices, then vertices constructed in different steps are distinguished by degree: all vertices in the clique have degree at least $3$, and all vertices in the independent set have degree $2$. (We ignore graphs on fewer than $4$ vertices, since there's only a few and we can easily tell when they're isomorphic.)

Therefore, if we have two graphs $G_1, G_2$ and construct split graphs $S_1, S_2$ in this way such that $S_1 \cong S_2$, the isomorphism must induce a bijection between the degree-$\ge 3$ side of $S_1$ and the degree-$\ge 3$ side of $S_2$. This bijection is actually an isomorphism between $G_1$ and $G_2$, since two vertices are adjacent in $G_i$ if and only if they have a common degree-$2$ neighbor in $S_i$. So we conclude that $G_1 \cong G_2$.

(Going the other way, if $G_1 \cong G_2$, our construction makes it easy to find an isomorphism between $S_1$ and $S_2$.)