GI-Completeness of graph isomorphism with connected graphs The Wikipedia page for Graph Isomorphism lists connected graphs as GI-complete. The citation has a paywall, and I have not been able to find any NP-complete algorithms for isomorphism of connected graphs.
Is this correct? Where can I find such an algorithm?
 A: GI-completeness is different from NP-completeness. (It is strongly believed that graph isomorphism is not NP-complete, though we don't yet know a polynomial-time algorithm.) A class of graphs is GI-complete if testing if graphs from this class are isomorphic is "as hard as" testing if general graphs are isomorphic.
Here is why graph isomorphism for connected graphs is GI-complete. Suppose that you have an algorithm that tests if two connected graphs are isomorphic, and you are given two graphs $G_1, G_2$ that are both not connected. You can still test them for isomorphism using your algorithm: let $H_i$ be a graph constructed from $G_i$ by adding a single vertex connected to all others. Then $H_1$ and $H_2$ are connected, so we can test if they are isomorphic using your algorithm. 
But $H_1 \cong H_2$ if and only if $G_1 \cong G_2$: the extra vertices we added are the only ones connected to all others, so they must be paired together in any isomorphism between $H_1$ and $H_2$, and deleting them both would produce an isomorphism between $G_1$ and $G_2$. Therefore your algorithm becomes a general algorithm for graph isomorphism.
