Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\W{\mathbb W}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cN{\mathcal N}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\cF{\mathcal F}
\def\cX{\mathcal X}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\newcommand{\pile}[1]{\bullet{#1}}
\def\g{g}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Chapter 9 Graph Isomorphisms
Graphs \(G=(V(G),E(G))\) and \(H=(V(H), E(H))\) are isomorphic when there is a bijection
\begin{equation*}
\phi: V(G) \rightarrow V(H)
\end{equation*}
such that
\begin{equation*}
(u,v) \in E(G) \Longleftrightarrow (\phi(u), \phi(v)) \in E(H).
\end{equation*}
In this case, we write \(G \cong H\text{.}\)
To prove that two graphs are isomorphic, you must explicitly give the mapping between the vertices.
To prove that two graphs are not isomorphic, you must find a structural property that they do not share. Here are some structural properties: the degree sequence, being bipartite, being connected, having a \(k\)-cycle, and more.
Exercises Practice Problems
1.
Draw two 3-regular graphs on 8 vertices, one of which is connected and one of which has two components. Solution.
Here is a 3-regular connected graph on 8 vertices (there are some other non-isomorphic graphs with these properties) and a 3-regular disconnected graph on 8 vertices (all such graphs are isomorphic to this one).
2.
Are the two graphs shown below isomorphic? If so, exhibit the isomorphism. If not, find a property that should be preserved by isomorphism for which the two graphs differ.
Solution. They are not isomorphic. The graph on the right has a 3-cycle, while the graph on the left does not. In fact, the graph on the left is bipartite.
3.
Draw the seven nonisomorphic subgraphs of \(K_3\text{.}\)
Solution.
4.
Prove that \(C_5 \cong \overline{C_5}\text{.}\) Can any other cycle graph be isomorphic to its complement? Justify your answer with example(s) or proof. Solution.
Both \(C_5\) and its complement are cycles on five vertices:
For a cycle \(C_n\text{,}\) the degree of each vertex is \(2\text{,}\) so the degree of each vertex in \(\overline{C}_n\) is \((n-1)-2=n-3\text{.}\) In order for \(C_n \cong \overline{C}_n\text{,}\) we must have \(2 = n-3\) and therefore \(n=5\text{.}\) In other words, \(C_5\) is the only cycles that is isomorphic to its complement.
5.
Are the three graphs shown below isomorphic? (Are any two of them isomorphic?) If so, exhibit the isomorphism. If not, find a property that should be preserved by isomorphism for which the two graphs differ.
The last graph is not isomorphic to the other two: every vertex has degree 4, while the vertices in the other two graphs each have degree 3. The first two graphs are isomorphic. We give one such isomorphism below.
