\include{preamble}
\setcounter{try}{48}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newenvironment{Ex}{\medskip \paragraph*{\emph{Example}.}}{\hfill \break $~\!\!$ \dotfill \medskip }
\title{}
\author{Zajj Daugherty}
\date{\today}
\usepackage{multicol}
\begin{document}
\begin{flushright}
SOLUTIONS\\
Homework 10\\
Due 5/1/19
\end{flushright}
%-----------------% HANDOUT 17 %-----------------%
\begin{try}
\begin{enumerate}[(a)]
\item Consider the graph
$$G=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) to (c) (d) to (a) to (c);
\end{tikzpicture}
\end{matrix}$$
\begin{enumerate}[(i)]
\item Give an example of a subgraph of $G$ that is not induced.
\begin{ans}
Take \emph{any} induced subgraph, and remove at least one additional edge. For example,
$$
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\draw (a) to (b) to (c) to (a);
\end{tikzpicture}
\end{matrix} \text{ ~is induced, \qquad so~ } \begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\draw (a) to (b) ;
\end{tikzpicture}
\end{matrix} \text{ ~is not induced.}$$
\end{ans}
\item How many induced subgraphs does $G$ have? List them.
\begin{ans}
There are 4 vertices, so there are $2^4$ induced subgraphs:
$$
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) to (c) (d) to (a) to (c);
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (b) to (c);
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (d) to (a) to (c);
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) (d) to (a);
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\draw (a) to (b) to (c) (a) to (c);
\end{tikzpicture}
\end{matrix}
$$
$$
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\end{tikzpicture}
\end{matrix}
\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\end{tikzpicture}
\end{matrix}
\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\draw (b) to (c);
\end{tikzpicture}
\end{matrix}
\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (d) to (a);
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\draw (a) to (c);
\end{tikzpicture}
\end{matrix}
\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,-.5) rectangle (1.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\draw (a) to (b);
\end{tikzpicture}
\end{matrix}
$$
$$
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,.5) rectangle (.5,1.5);
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,.5) rectangle (.5,1.5);
\node[bV, label=above:{\tiny$b$}] (a) at (0,1) {};
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,.5) rectangle (.5,1.5);
\node[bV, label=above:{\tiny$c$}] (a) at (0,1) {};
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,.5) rectangle (.5,1.5);
\node[bV, label=above:{\tiny$d$}] (a) at (0,1) {};
\end{tikzpicture}
\end{matrix}
\qquad\qquad
\begin{matrix}
\begin{tikzpicture}[scale=1]
\draw[dotted] (-.5,.5) rectangle (.5,1.5);
\end{tikzpicture}
\end{matrix}
$$
\end{ans}
\item How many subgraphs does $G$ have?
\begin{ans}
A graph with $m$ edges has exactly $2^m$ subgraphs with the same vertex set. So, going through the induced subgraphs (the largest subgraph of $G$ with each possible vertex set), we get
$$2^4 + 2 + 2^2 + 2^2 + 2^3 + 1 + 1 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = \fbox{49}$$
subgraphs of $G$ in total.
\end{ans}
\pagebreak
\item Let $e$ be the edge connecting $a$ and $d$. Draw $G - e$, $G/e$, and $(G/e)_{\mathrm{simple}}$.
\begin{ans}
We have
$$G - e =
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) to (c) (a) to (c);
\end{tikzpicture}
\end{matrix} \qquad\text{and}\qquad
G/e = (G/e)_{\mathrm{simple}}
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a, d$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\draw (a) to (b) to (c) (a) to (c);
\end{tikzpicture}
\end{matrix}.
$$
\end{ans}
\item Let $e$ be the edge connecting $a$ and $c$. Draw $G - e$, $G/e$, and $(G/e)_{\mathrm{simple}}$.
\begin{ans}
We have
$$G-e=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) to (c) (d) to (a);
\end{tikzpicture}
\end{matrix},
\qquad
G/e=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a,c$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) (d) to (a) (b) to [bend right] (a);
\end{tikzpicture}
\end{matrix}
\qquad \text{and}\qquad
(G/e)_{\mathrm{simple}}
=\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a,c$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) (d) to (a);
\end{tikzpicture}
\end{matrix}.$$
\end{ans}
\item Draw $\bar{G}$.
\begin{ans}
The complement of $G$ is
$$G=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (b) to (d) to (c);
\end{tikzpicture}
\end{matrix}.$$
\end{ans}
\end{enumerate}
\item Show that $$G=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (b) to (c) (d) to (a) ;
\end{tikzpicture}
\end{matrix}$$
is isomorphic to its complement.
\begin{ans}
Since
$$\bar{G}=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\node[bV, label=above:{\tiny$a$}] (a) at (0,1) {};
\node[bV, label=below:{\tiny$b$}] (b) at (0,0) {};
\node[bV, label=below:{\tiny$c$}] (c) at (1,0) {};
\node[bV, label=above:{\tiny$d$}] (d) at (1,1) {};
\draw (a) to (c) to (d) to (b) ;
\end{tikzpicture}
\end{matrix}$$
the map
$$d \mapsto a, \qquad a \mapsto c, \qquad b \mapsto d, \qquad c \mapsto b,$$
gives an isomorphism.
\end{ans}
\pagebreak
\item Find a simple graph with 5 vertices that is isomorphic to its own complement. (Start with: how many edges must it have?)
\begin{ans}
To get going, recall that isomorphisms must preserve the number of edges. We also know that and if $G$ has $n$ vertices, then $|E(\overline{G})| = \binom{n}{2} - |E({G})|$. So if $\overline{G} \cong {G}$ and $G$ has 5 vertices and $m$ edges, we need
$$m = \binom{5}{2} - m = 10 - m, \qquad \text{so that $m = 10$}.$$
Further, since degree sequences have to be preserved, and for any vertex $v$ in $G$, we have $\deg_{\overline{G}}(v) = n-1 - \deg_G(v)$. So if $d_1, d_2, d_3, d_4, d_5$ is the degree sequence of $G$, then $4- d_1, 4-d_2, 4-d_3, 4-d_4, 4-d_5$ must be a rearrangement of $d_1, d_2, d_3, d_4, d_5$. In particular, we can't have any isolated vertices, since that would also mean that we would have to have a vertex of degree 4 (meaning that it would have to be connected to every other vertex), and vice versa (i.e. $1 \le d_i \le 3$ for each $i = 1,2,3,4,5$). In particular, the only possible degree sequences are
$$(2,2,2,2,2) \qquad (3,2,2,2,1), \quad \text{ and } \quad (3,3,2,1,1). $$
This means that the connected components either have to be the whole graph or have 2 and 3 vertices each. But the most edges that a graph of the latter type could have is $|E(K_3)| + |E(K_2)| = 3 + 1 = 4 < 5$. So our graph \emph{has} to be connected!
Up to isomorphism, the only simple connected graph of degree sequence $(2,2,2,2,2)$ is $C_5$:
$$C_5=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x*360/5 + 90:1cm) {};}
\node[above] at (5) {\tiny $5$};
\node[left] at (1) {\tiny $1$};
\node[left] at (2) {\tiny $2$};
\node[right] at (3) {\tiny $3$};
\node[right] at (4) {\tiny $4$};
\draw (5) to (1) to (2) to (3) to (4) to (5);
\end{tikzpicture}
\end{matrix} \cong \bar{C_5}=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x*360/5 + 90:1cm) {};}
\node[above] at (5) {\tiny $5$};
\node[left] at (1) {\tiny $1$};
\node[left] at (2) {\tiny $2$};
\node[right] at (3) {\tiny $3$};
\node[right] at (4) {\tiny $4$};
\draw (5) to (2) to (4) to (1) to (3) to (5);
\end{tikzpicture}
\end{matrix}$$
by $1 \mapsto 1$,
$2 \mapsto 3$,
$3 \mapsto 5$,
$4 \mapsto 2$, and
$5 \mapsto 4$.
Similarly, up to isomorphism, the only simple connected graph of degree sequence $(3,3,2,1,1)$ is
$$G=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x*360/5 + 90:1cm) {};}
\node[above] at (5) {\tiny $5$};
\node[left] at (1) {\tiny $1$};
\node[left] at (2) {\tiny $2$};
\node[right] at (3) {\tiny $3$};
\node[right] at (4) {\tiny $4$};
\draw (2) to (5) to (3) to (2) to (1) (3) to (4);
\end{tikzpicture}
\end{matrix} \cong \bar{G}=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x*360/5 + 90:1cm) {};}
\node[above] at (5) {\tiny $5$};
\node[left] at (1) {\tiny $1$};
\node[left] at (2) {\tiny $2$};
\node[right] at (3) {\tiny $3$};
\node[right] at (4) {\tiny $4$};
\draw (1) to (5) to (4) to (1) to (3) (4) to (2);
\end{tikzpicture}
\end{matrix}$$
by $1 \mapsto 3$,
$2 \mapsto 1$,
$3 \mapsto 4$,
$4 \mapsto 2$, and
$5 \mapsto 5$.
Up to isomorphism, there are two simple connected graphs of degree sequence $(3,2,2,2,1)$:
$$H=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x*360/5 + 90:1cm) {};}
\node[above] at (5) {\tiny $5$};
\node[left] at (1) {\tiny $1$};
\node[left] at (2) {\tiny $2$};
\node[right] at (3) {\tiny $3$};
\node[right] at (4) {\tiny $4$};
\draw (1) to (2) to (3) to (4) to (1) to (5);
\end{tikzpicture}
\end{matrix} \quad \text{and} \quad \bar{H}=
\begin{matrix}
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x*360/5 + 90:1cm) {};}
\node[above] at (5) {\tiny $5$};
\node[left] at (1) {\tiny $1$};
\node[left] at (2) {\tiny $2$};
\node[right] at (3) {\tiny $3$};
\node[right] at (4) {\tiny $4$};
\draw (1) to (3) (2) to (4) (2) to (5) (3) to (5) (4) to (5);
\end{tikzpicture}
\end{matrix} =
\begin{matrix}
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x*360/5 + 90:1cm) {};}
\node[above] at (5) {\tiny $3$};
\node[left] at (1) {\tiny $5$};
\node[left] at (2) {\tiny $2$};
\node[right] at (3) {\tiny $4$};
\node[right] at (4) {\tiny $1$};
\draw (1) to (2) to (3) to (1) to (5) to (4);
\end{tikzpicture}
\end{matrix}.$$
You can see that they are not isomorphic because in $H$, the vertex of degree 1 is adjacent to the vertex of degree 3; but in $\bar{H}$, the degree-1 vertex is adjacent to a vertex of degree 2.
\end{ans}
\end{enumerate}
\end{try}
\begin{try} Let $G$ be the graph
$$\begin{matrix}\begin{tikzpicture}
\node[bV, label=above:{\tiny$b$}] (b) at (1,1) {};
\node[bV, label=above:{\tiny$c$}] (c) at (2,1) {};
\node[bV, label=above:{\tiny$d$}] (d) at (3,1) {};
\node[bV, label=below:{\tiny$a$}] (a) at (0,0) {};
\node[bV, label=above right:{\tiny$g$}] (g) at (1,0) {};
\node[bV, label=below:{\tiny$f$}] (f) at (2,0) {};
\node[bV, label=below:{\tiny$e$}] (e) at (3,0) {};
\draw (a) to (b) to (c) to (d) to (e) to (c) to (f) to (d) (e) to (f) to (g) to (a) to [bend right] (f) (g) to (b);
\end{tikzpicture}\end{matrix}$$
Note that $G$ is simple, so that walks in $G$ are determined by sequences of vertices.
\begin{enumerate}[(a)]
\item Decide which of the following sequences of vertices determine walks. For those that are walks, decide whether they can be classified more finely (is it a circuit, a path, a cycle, or a a trail?).
\begin{enumerate}[(i)]
\item $a,b,g,f,c,b$
\Ans{Trail}
\item $b,g,f,c,b,g,a$
\Ans{WAlk}
\item $c,e,f,c$
\Ans{Cycle}
\item $c,e,f,c,e$
\Ans{Walk}
\item $a,b,f,a$
\Ans{Not a walk}
\item $f,d,e,c,b$
\Ans{Path}
\end{enumerate}
\item Verify that the following sequences of vertices determine paths. Decide whether they are maximal. If not, extend the sequence to a maximal path.
\begin{enumerate}[(i)]
\item $a,b,g,f,d$
\Ans{
This is not maximal: $a,b,g,f,d, e,c$ is.
}
\item $d,e,f,c,b,a,g$
\Ans{
This is maximal.}
\item $f,a,g,b,c$
\Ans{
This is not maximal: $e,f,a,g,b,c,d$ is.}
\end{enumerate}
\item Give an example of a maximal path whose length is not maximal (a path that cannot be extended, but which is shorter than some other path in $G$).
\begin{ans}
For example, $d,c,f,e$ is maximal, but is shorter in length than, say, $e,f,a,g,b,c,d$.
\end{ans}
\end{enumerate}
\end{try}
\begin{try}~
\begin{enumerate}[(a)]
\item For each pair of graphs, either use paths or cycles to show that they are not isomorphic, or give an isomorphism.
\begin{ans}~
\centerline{\includegraphics[width=5.5in]{path-graphs}}
\noindent \textbf{(i)} These graphs are not isomorphic because the one on the right has a 7-cycle (e.g.\ $v_1$, $v_2$, $v_3$, $v_7$, $v_6$, $v_5$, $v_1$), but the one on the left doesn't (it's bipartite, with $V_1 = \{u_1, u_6, u_8, u_3\}$ and $V_2=\{u_2, u_4, u_5, u_7\}$, so cannot have an odd-length cycle).
\medskip
\noindent \textbf{(ii)} These are not isomorphic because the left has a 5-cycle ($u_2, u_3, u_4, u_5, u_6, u_2$) and the one of the right is bipartite (with $V_1 = \{v_1, v_3, v_5, v_7\}$ and $V_2 = \{v_2, v_4, v_6, v_8\}$), and therefore cannot have any 5-cycles.
\pagebreak
\centerline{\includegraphics[width=5.5in]{path-graphs2}}
\noindent \textbf{(ii)} Notice that both graphs have two 5-cycles that share a single edge as follows:
$$\begin{matrix}\begin{tikzpicture}
\foreach \x in {0,1,2,3,4,5,6,7,8}{\node[bV, label=157.5-\x*45:{$u_\x$}] (\x) at (157.5-\x*45:1.5cm){};}
\draw[thin] (1) to (2) to (3) to (4) to (5) to (6) to (7) to (8) to (1) to (3) (2) to (5) (4) to (7) (6) to (8);
\draw[very thick, red] (1) to (2) to (5) to (6) to (8);
\draw[very thick, red!50!blue] (1) to (8);
\draw[very thick, blue] (1) to (3) to (4) to (7) to (8);
\end{tikzpicture}\end{matrix}
\qquad \qquad
\begin{matrix}\begin{tikzpicture}
\foreach \x in {0,1,2,3,4,5,6,7,8}{\node[bV, label=157.5-\x*45:{$v_\x$}] (\x) at (157.5-\x*45:1.5cm){};}
\draw[thin] (1) to (2) to (3) to (4) to (5) to (6) to (7) to (8) to (1) to (3) (2) to (6) (4) to (8) (5) to (7);
\draw[very thick, red] (2) to (1) to (8) to (7) to (6);
\draw[very thick, red!50!blue] (2) to (6);
\draw[very thick, blue] (2) to (3) to (4) to (5) to (6);
\end{tikzpicture}\end{matrix}
$$
Then, walking around the two cycles, the only other edges form bijections between the non-shared vertices of the two cycles. This shows us the bijection
$$u_1 \mapsto v_2, \quad u_2 \mapsto v_1, \quad u_5 \mapsto v_8,\quad u_6 \mapsto v_7, $$
$$u_8 \mapsto v_6, \quad u_3 \mapsto v_3, \quad u_4 \mapsto v_4, \quad u_7 \mapsto v_5.$$
\medskip
\noindent \textbf{(iv)} Lining up the back face (upper right square) of the first graph with the outer cycle of the right graph, and the front face (lower left square) of the first graph with the inner cycle of the right graph, we can see that these are isomorphic via the map
$$u_1 \mapsto v_1, \quad u_2 \mapsto v_2, \quad u_3 \mapsto v_3, \quad u_4 \mapsto v_8,$$
$$u_5 \mapsto v_5, \quad u_6 \mapsto v_6, \quad u_7 \mapsto v_2, \quad u_8 \mapsto v_4.$$
\end{ans}
\item Explain why if $v$ is a vertex of odd degree, then there is a walk from $v$ to another vertex of odd degree.
\begin{ans}
By the Handshake Theorem, every graph has an even number of odd degree vertices. Notice that each connected component is an induced subgraph with the same degrees. So each connected component also has an even number of odd degree vertices. So if a connected component has an odd degree vertex, it must have two. So those two vertices are connected by a walk.
\end{ans}
\end{enumerate}
\end{try}
\pagebreak
%-----------------% HANDOUT 18 %-----------------%
\begin{try}~
\begin{enumerate}[(a)]
\item For each of the following graphs, compute the vertex and edge connectivity. Be sure to justify your answers.
\begin{ans}
$$G_1 = \begin{matrix}\begin{tikzpicture}
\foreach \x/\y in {0/a, 1/b, 2/c, 3/d} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/g, 1/f, 2/e} {\node[bV, label=below:{$\y$}] (\y) at (\x,0){};}
\draw (a) to (b) to (f) to (e) to (c) to (d) to (e) to (b) to (g)to (f) to (a);
\end{tikzpicture}\end{matrix}$$
\begin{enumerate}[{vertex}]
\item[\bf Vertex:] $G_1$ is connected, and $e$ is a cut vertex. So $\kappa(G_1) = 1$.
\item[\bf Edge:] Every edge is part of a cycle--$(a,b,e,f,a)$, $(b,f,g,b)$, or $(c,d,e,c)$--so $\lambda(G_1) \ge 2$. And $\{c-d, d-e\}$ is an edge cut. So $\lambda(G_1)=2$.
\end{enumerate}
$$G_2 = \begin{matrix}\begin{tikzpicture}
\foreach \x/\y in {0/a, 1/b, 2/c, 3/d} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/h, 1/g, 2/f, 3/e} {\node[bV, label=below:{$\y$}] (\y) at (\x,0){};}
\draw (a) to (b) to (h) to (g) to (c) to (b) (d) to (e) (b) to (f) to (g) to (a) (f) to (c);
\end{tikzpicture}\end{matrix}$$
Since $G_2$ is not connected, we have $\kappa(G_2) = 0 = \lambda(G_2)$.
\medskip
$$G_3 = \begin{matrix}\begin{tikzpicture}[scale=1.5]
\foreach \x/\y in {0/a, 1/b, 2/c} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/d, 1/e, 2/f} {\node[bV, label=below right:{$\y$}] (\y) at (\x,0){};}
\foreach \x/\y in {0/g, 1/h, 2/i} {\node[bV, label=below:{$\y$}] (\y) at (\x,-1){};}
\draw (a) to (c) to (i) to (g) to (a) (d) to (f) (b) to (h) (d) to (b) (h) to (f);
\end{tikzpicture}\end{matrix}$$
\begin{enumerate}[{vertex}]
\item[\bf Edge:] Every edge is a part of a cycle--$(a,b,c,f,i,h,g,d,a)$, $(b,e,d,b)$, or $(e,f,h,e)$--so $\lambda(G_3) \ge 2$. And $\{a-b, a-d\}$ is an edge cut. So $\lambda(G_3)=2$.
\item[\bf Vertex:] As a consequence of the argument above, every vertex is part of a cycle, so $\kappa(G_3)\ge2$. So since $\{b,d\}$ is a vertex cut, we have $\kappa(G_3)=2$.
\end{enumerate}
$$G_4 = \begin{matrix}\begin{tikzpicture}[scale=1.5]
\foreach \x/\y in {0/a, 1/b, 2/c, 3/d} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/i, 1/h, 2/g, 4/f, 3/e} {\node[bV, label=below:{$\y$}] (\y) at (\x,0){};}
\draw (c) to [bend right=60] (a) to (h) to (b) to (i) to (c) to (g) to (i) to (a) to (d) to (e) to (f)
(g) to (d) to (h) to [bend right=60] (e) (g) to [bend right=60] (f);
\end{tikzpicture}\end{matrix}$$
Similarly to $G_1$ and $G_3$, every edge is in a cycle, so $\lambda(G_4) \ge \kappa(G_4) \ge 2$. But $\deg(f) = 2$, so $2 \ge \lambda(G_4) \ge \kappa(G_4) \ge 2$. Thus $ \lambda(G_4) = \kappa(G_4) = 2$.
\end{ans}
\item Recall that $\kappa(G)$ is the vertex connectivity of $G$ and $\lambda(G)$ is the edge connectivity of $G$. Give examples of graphs for which each of the following are satisfied.
\begin{center}
\fbox{\bf Throughout, let $\delta(G) = \min_{v \in V} \deg(v)$.}
\end{center}
\begin{enumerate}[(i)]
\item $\kappa(G) = \lambda(G)<\delta(G)$
\begin{Ex}
$$
\begin{matrix}\begin{tikzpicture}
\node[bV] (a) at (0,.5){};
\node[bV] (b) at (0, -.5){};
\node[bV] (c) at (1,0){};
\node[bV] (d) at (2,0){};
\node[bV] (e) at (3, .5){};
\node[bV] (f) at (3, -.5){};
\draw (a) to (b) to (c) to (a) (c) to (d) to (e) to (f) to (d);
\end{tikzpicture}\end{matrix}
\qquad \kappa = \lambda = 1, \delta = 2.
$$
\end{Ex}
\item $\kappa(G) < \lambda(G) = \delta(G)$
\begin{Ex}
$$
\begin{matrix}\begin{tikzpicture}
\node[bV] (a) at (0,.5){};
\node[bV] (b) at (0, -.5){};
\node[bV] (c) at (1,0){};
\node[bV] (e) at (2, .5){};
\node[bV] (f) at (2, -.5){};
\draw (a) to (b) to (c) to (a) (c) to (e) to (f) to (c);
\end{tikzpicture}\end{matrix}
\qquad \kappa = 1, \lambda = 2, \delta = 2.
$$
\end{Ex}
\item $\kappa(G) < \lambda(G) < \delta(G)$
\begin{Ex}
$$
\begin{matrix}\begin{tikzpicture}
\node[bV] (x) at (-1,.5){};
\node[bV] (y) at (-1, -.5){};
\node[bV] (a) at (0,.5){};
\node[bV] (b) at (0, -.5){};
\node[bV] (c) at (1,0){};
\node[bV] (e) at (2, .5){};
\node[bV] (f) at (2, -.5){};
\node[bV] (g) at (3, .5){};
\node[bV] (h) at (3, -.5){};
\draw (a) to (x) (y) to (b) to (x) to (y) to (a) to (b) to (c) to (a) (c) to (e) to (f) to (c) (e) to (h) to (g) to (f) to (h) (e) to (g);
\end{tikzpicture}\end{matrix}
\qquad \kappa =1, \lambda = 2, \delta = 3.
$$
\end{Ex}
\item $\kappa(G) = \lambda(G) = \delta(G)$
\begin{Ex}
All cycles of length 3 or more have $\kappa = \lambda = \delta = 2$.
\end{Ex}
\end{enumerate}
\item For which values of $m$ and $n$ does the complete bipartite graph $K_{m, n}$ have a cut vertex? A cut edge? What is are $\kappa(K_{m,n})$ and $\lambda(K_{m,n})$?
\begin{ans}
If $K_{m,n}$ has a cut vertex or a cut edge, then $n$ or $m$ are equal to 1. This is because
$$\kappa(K_{m,n}) = \min(m,n) = \lambda(K_{m,n}).$$
For the vertex connectivity, the best you can do is remove all of the vertices from the smaller part. For edge connectivity, the best you can do is remove all of the edges incident to one of the vertices in the smaller part.
\end{ans}
\item For which values of $n$ does the wheel $W_n$ have a cut vertex? A cut edge? What is are $\kappa(W_n)$ and $\lambda(W_n)$?
\begin{ans}
The wheel never has a cut vertex or a cut edge. This is because
$$\kappa(W_n) = 3 = \lambda(W_n).$$
For the vertex connectivity: the best you can do is remove the middle vertex to get a cycle, and then remove two vertices to disconnect the cycle. For edge connectivity, the best you can do is remove all of the edges incident to one of outer vertices.
\end{ans}
\end{enumerate}
\end{try}
\pagebreak
\begin{try}(Euler trails and circuits)
\begin{enumerate}[(a)]
\item Decide which of the following graphs have Eulerian circuits, which have Eulerian trails, and which have neither. For those that have an Eulerian circuits or trails, give an example.
\begin{ans}~
$$\begin{matrix}\begin{tikzpicture}
\foreach \x/\y in {0/a, 1/b, 2/c, 3/d} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/g, 1/f, 2/e} {\node[bV, label=below:{$\y$}] (\y) at (\x,0){};}
\draw (a) to (b) to (f) to (e) to (c) to (d) to (e) to (b) to (g)to (f) to (a);
\end{tikzpicture}\end{matrix}$$
This has an Eulerian circuit: $b,a,f,b,g,f,e,c,d,e,b$.
\noindent{}\dotfill
\medskip
$$\begin{matrix}\begin{tikzpicture}
\foreach \x/\y in {0/a, 1/b, 2/c, 3/d} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/h, 1/g, 2/f, 3/e} {\node[bV, label=below:{$\y$}] (\y) at (\x,0){};}
\draw (a) to (b) to (h) to (g) to (c) to (d) to (e) to (f) to (g) to (a) (f) to (c) (a) to (h);
\end{tikzpicture}\end{matrix}$$
This does not have an Eulerian trail (or circuit) since it has more than two vertices of odd degree.
\noindent{}\dotfill
\medskip
$$\begin{matrix}\begin{tikzpicture}
\foreach \x/\y in {0/a, 1/b, 2/c, 3/d} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/h, 1/g, 2/f, 3/e} {\node[bV, label=below:{$\y$}] (\y) at (\x,0){};}
\draw (a) to (b) to (h) to (g) to (c) to (d) to (e) to (f) to (g) to (a) (f) to (c);
\end{tikzpicture}\end{matrix}$$
This has an Eulerian trail, but not a circuit, since it has two vertices of odd degree. One trail is $c,d,e,f,g,a,b,h,g,f$.
\noindent{}\dotfill
\medskip
$$\begin{matrix}\begin{tikzpicture}[scale=1.5]
\foreach \x/\y in {0/a, 1/b, 2/c, 3/d} {\node[bV, label=above:{$\y$}] (\y) at (\x,1){};}
\foreach \x/\y in {0/i, 1/h, 2/g, 4/f, 3/e} {\node[bV, label=below:{$\y$}] (\y) at (\x,0){};}
\draw (c) to [bend right=60] (a) to (h) to (b) to (i) to (c) to (g) to (i) to (a) to (d) to (e) to (f)
(g) to (d) to (h) to [bend right=60] (e) (g) to [bend right=60] (f);
\end{tikzpicture}\end{matrix}$$
This doesn't have an Eulerian circuit since $e$ and $c$ have odd degree. But it does have an Eulerian trail: $e, f, g, d, e, h, g, c, d, h, b, c, i, h, a, i, b, a, c$.
\end{ans}
\pagebreak
\item For which values of $m$, $n$ do the following have an Euler trail? an Euler circuit?
\begin{enumerate}[(i)]
\item $K_n$
\begin{ans}
Since $K_n$ is regular of degree $n-1$, we have $K_n$ has Euler circuits for $n$ odd, and no Euler trail for $n$ even (except for $n=2$).
\end{ans}
\item $Q_n$
\begin{ans}
Since $Q_n$ is regular of degree $n$, we have $Q_n$ has Euler circuits for $n$ even, and no Euler trail for $n$ odd (except for $n=1$).
\end{ans}
\item $K_{m,n}$
\begin{ans}
Note that $K_{m,n}$ has $n$ vertices of degree $m$, and $m$ vertices of degree $n$. So $K_{m,n}$ has an Euler trail whenever $m$ and $n$ are both even, or when one of $m$ or $n$ is odd, and the other is equal to 2. It has an Euler circuit when both $m$ and $n$ are even.
\end{ans}
\end{enumerate}
\end{enumerate}
\end{try}
\begin{try}(Hamilton paths and cycles)
\begin{enumerate}[(a)]
\item Decide which of the following has a Hamilton path, a Hamilton cycle, or neither. If a cycle of path exists, give an example. If not, give an argument as to why not.
\begin{enumerate}[(i)]
\item
$$\begin{matrix}\begin{tikzpicture}
\node[bV, label=above:{$a$}] (a) at (0,1){};
\node[bV, label=below:{$b$}] (b) at (0,-1){};
\node[bV, label=left:{$c$}] (c) at (1,0){};
\node[bV, label=right:{$d$}] (d) at (2,0){};
\node[bV, label=above:{$e$}] (e) at (3,1){};
\node[bV, label=below:{$f$}] (f) at (3,-1){};
\draw (c) to (b) to (a) to (c) to (d) to (e) to (f) to (d);
\end{tikzpicture}\end{matrix}$$
\begin{ans}
This doesn't have a Hamilton cycle, because it has a cut vertex, $d$. But it does have a Hamilton path--$a,b,c,d,e,f$.
\end{ans}
\item
$$
\begin{matrix}\begin{tikzpicture}[scale=1.5]
\node[bV, label=above:{$a$}] (a) at (0,1){};
\node[bV, label=below:{$b$}] (b) at (0,0){};
\node[bV, label=below left:{$c$}] (c) at (.5,.5){};
\node[bV, label=above:{$d$}] (d) at (1,1){};
\node[bV, label=below:{$e$}] (e) at (1,0){};
\node[bV, label=below:{$f$}] (f) at (2,0){};
\draw (a) to (b) to (e) to (c) to (a) to (d) to (e) to (f) (c) to (d);
\end{tikzpicture}\end{matrix}$$
\begin{ans}
Again, this doesn't have a Hamilton cycle, because it has a cut vertex, $e$. But it does have a Hamilton path--$c,d,a,b,e,f$.
\end{ans}
\item
$$
\begin{matrix}\begin{tikzpicture}[scale=1.5]
\node[bV, label=above:{$a$}] (a) at (0,1){};
\node[bV, label=below:{$b$}] (b) at (0,0){};
\node[bV, label=below left:{$c$}] (c) at (.5,.5){};
\node[bV, label=above:{$d$}] (d) at (1,1){};
\node[bV, label=below:{$e$}] (e) at (1,0){};
\node[bV, label=below:{$f$}] (f) at (2,0){};
\node[bV, label=above:{$g$}] (g) at (2,1){};
\draw (a) to (b) to (e) to (c) to (a) to (d) to (e) to (f) (c) to (d) to (g) to (f);
\end{tikzpicture}\end{matrix}
$$
\end{enumerate}
\begin{ans}
This graph has a Hamilton cycle--$a,c,d,g,f,e,b,a$--and hence also has a Hamilton path.
\end{ans}
\item For which values of $m$, $n$ do the following have an Hamilton path? a Hamilton cycle?
$$\text{(i)}~ K_n \qquad \text{(ii)}~ Q_n \qquad \text{(iii)}~ K_{m,n}$$
\begin{enumerate}[(i)]
\item $K_n$
\begin{ans}
For all $n \ge 3$, $K_n$ contains a $C_n$: labeling the vertices $\{1,2,\dots, n\}$, since $K_n$ has every possible edge, it has the edges for the cycle $(1,2,3, \dots, n,1)$, which is a Hamilton cycle. Therefore it also has a Hamilton path.
For $n=1$ and $2$, there are no cycles as subgraphs, but $K_1$ and $K_2$ are paths, and so have Hamilton paths.
\end{ans}
\item $Q_n$
\begin{ans}
Since $Q_1 = P_2$, $Q_1$ has a Hamilton path but not a cycle.
We'll show that all $Q_n$ for $n\ge 2$ has a Hamilton cycle (and therefore a Hamilton path) by induction on $n$ as follows.
\begin{proof}
For $Q_2$, the walk $00, 01, 11, 10, 00$ is a Hamilton cycle. This establishes our base case.
Now fix $n \ge 2$ and assume $Q_n$ has a Hamilton cycle $w_1, w_2, \dots, w_\ell, w_1$. \emph{(In short, we'll take the corresponding Hamilton path, and find two copies of it in $Q_{n+1}$ and glue them together to get a Hamilton cycle.)}
Recall the vertices of $Q_n$ are words in $0$'s and $1$'s of length $n$, so $\ell = 2^n$ and the $w_i$'s are all words. Note that if the words $w$ and $w'$ are adjacent in $W_n$, meaning that they differ in exactly one bit, then $0w$ and $0w'$ are adjacent in $Q_{n+1}$, as are $1w$ and $1w'$. Thus
$$0w_1, 0w_2, \dots, 0w_\ell \quad \text{ and } \quad 1w_1, 1w_2, \dots, 1w_\ell$$
are both paths in $Q_{n+1}$, and are disjoint from eachother. Moreover, $0w_1$ and $1w_1$ differ in exactly one bit, so are adjacent; same for $0w_\ell$ and $1w_\ell$. Therefore
$$0w_1, 0w_2, \dots, 0w_\ell, 1w_\ell, 1w_{\ell-1}, \dots, 1w_2, 1w_1, 0w_1$$
is a cycle in $Q_{n+1}$. And since it has $2*|V(Q_n)| = 2*2^n = 2^{n+1}$ vertices, which is how many vertices $Q_{n+1}$ has, we must have covered all of them in the cycle. Thus it's a Hamilton cycle, as desired.
\end{proof}
\emph{As an example of the inductive step in this proof, $Q_2$ has the cycle
$$w_1 = 00, w_2 = 01, w_3 = 11, w_4 = 10, w_1 = 00.$$
Then the two corresponding paths in $Q_3$ are
$$000, 001, 011, 010 \qquad \text{and} \qquad 100, 101, 111, 110.$$
Walking forward along the first and then backward along the second gives the cycle
$$000, 001, 011, 010, 110, 111, 101, 100, 000,$$
as desired.
}
\end{ans}
\item $K_{m,n}$
\begin{ans}
Since any walk through $K_{m,n}$ has to alternate between the two parts, we can only cover all the vertices with a cycle if $m=n$; or with a path if $m=n+1$. And since every edge between the two parts is available, we can create such cycles and paths. So $K_{m,n}$ has a Hamilton cycle if and only if $m=n$; and has a Hamilton path if and only if $m=n$ or $m=n+1$.
\end{ans}
\end{enumerate}
\item The \emph{Petersen graph} is
$$P=
\begin{matrix}\begin{tikzpicture}
\foreach \x in {0,1,2,3,4} { \node[bV] (I\x) at (\x*360/5 + 90:1){}; \node[bV] (O\x) at (\x*360/5 + 90:2){};}
\draw (O0) to (O1) to (O2) to (O3) to (O4) to (O0)
(O0) to (I0) (O1) to (I1) (O2) to (I2) (O3) to (I3) (O4) to (I4)
(I0) to (I2) to (I4) to (I1) to (I3) to (I0);
\end{tikzpicture}\end{matrix}
$$
Argue that it does not have a Hamilton cycle, but the induced subgraph $G - v$, for any $v \in V$, does.
\def\Pet{\foreach \x in {0,1,2,3,4} { \node[bV] (I\x) at (\x*360/5 + 90:1){}; \node[bV] (O\x) at (\x*360/5 + 90:2){};}
\draw (O0) to (O1) to (O2) to (O3) to (O4) to (O0)
(O0) to (I0) (O1) to (I1) (O2) to (I2) (O3) to (I3) (O4) to (I4)
(I0) to (I2) to (I4) to (I1) to (I3) to (I0);
}
\begin{ans}
Note that deleting any one vertex in the Petersen graph leaves the same underlying isomorphism type of graph. And the resulting graph has a Hamilton cycle:
$$
\begin{matrix}\begin{tikzpicture}
\foreach \x in {0,1,2,3,4} { \node[bV] (I\x) at (\x*360/5 + 90:1){}; \node[bV] (O\x) at (\x*360/5 + 90:2){};}
\node[bV, white] at (O0) {x};
\draw (O1) to (O2) to (O3) to (O4)
(I0) (O1) to (I1) (O2) to (I2) (O3) to (I3) (O4) to (I4)
(I0) to (I2) to (I4) to (I1) to (I3) to (I0);
\draw[line width = 2.5pt, blue] (O1) to (I1) to (I4) to (O4) to (O3) to (I3) to (I0) to (I2) to (O2) to (O1);
\end{tikzpicture}\end{matrix}.
$$
Now consider $P$ itself. The rotation of $P$ by any $k(2\pi/5)$ (for $k \in \ZZ$) leaves the unlabeled graph fixed, as does the horizontal flip. To get between the inner vertices and the outer vertices, we have to include at least one of those edges (which is arbitrary by the previous sentence); and if we're building a cycle, it needs to be incident to to at least one edge on each end. Up to a horizontal flip, this means we either have
$$\begin{matrix}\begin{tikzpicture}
\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);
\end{tikzpicture}\end{matrix} \qquad \text{ or } \qquad
\begin{matrix}\begin{tikzpicture}
\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
\end{tikzpicture}\end{matrix}
$$
as part of our cycle. Extending the first case little by little (at either end of the path already traced, take a step---don't revisit any vertices until we've visited all 10; keep walking if any next steps are forced), we can see that we're forced into a corner no matter what choices we make:
$$\TikZ{[yscale=3, xscale=2]
\coordinate (1) at (0,0);
\coordinate (11) at (-2,-1);
\coordinate (12) at (2,-1);
\coordinate (111) at (-3,-2);
\coordinate (112) at (-1,-2);
\coordinate (121) at (1,-2);
\coordinate (122) at (3,-2);
\draw (11) to (1) to (12);
\draw (111) to (11) to (112);
\draw (121) to (12) to (122);
\node[fill=white] at (1) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);}$};
\node[fill=white] at (11) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);
\draw[line width = 2.5pt, red]
(O1) to (O2) to (O3)
(I2) to (I4);}$};
\node[fill=white] at (12) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);
\draw[line width = 2.5pt, red]
(I2) to (O2) to (O3) (O1) to (I1);}$};
\node[fill=white] at (111) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);
\draw[line width = 2.5pt, red]
(O1) to (O2) to (O3)
(I2) to (I4);
\draw[line width = 2.5pt, green]
(O3) to (O4) (I4) to (I1) to (I3);
\node at (0,-2.5) {\tiny(no extension to a cycle)};
}$};
\node[fill=white] at (112) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);
\draw[line width = 2.5pt, red]
(O1) to (O2) to (O3)
(I2) to (I4);
\draw[line width = 2.5pt, green]
(I4) to (O4) (O3) to (I3) to (I1);
\node at (0,-2.5) {\tiny(no extension to a cycle)};
}$};
\node[fill=white] at (121) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);
\draw[line width = 2.5pt, red]
(I2) to (O2) to (O3) (O1) to (I1);
\draw[line width = 2.5pt, green]
(I1) to (I4) to (O4) (O3) to (I3);
\node at (0,-2.5) {\tiny(no extension to a cycle)};}$};
\node[fill=white] at (122) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I2);
\draw[line width = 2.5pt, red]
(I2) to (O2) to (O3) (O1) to (I1);
\draw[line width = 2.5pt, green]
(I1) to (I3) (O3) to (O4) to (I4);
\node at (0,-2.5) {\tiny(no extension to a cycle)};}$};
}$$
Similarly for the second case, extending little by little gives
$$\TikZ{[yscale=3, xscale=2]
\coordinate (1) at (0,0);
\coordinate (11) at (-2,-1);
\coordinate (12) at (2,-1);
\coordinate (111) at (-3,-2);
\coordinate (112) at (-1,-2);
\coordinate (121) at (1,-2);
\coordinate (122) at (3,-2);
\draw (11) to (1) to (12);
\draw (111) to (11) to (112);
\draw (121) to (12) to (122);
\node[fill=white] at (1) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
}$};
\node[fill=white] at (11) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
\draw[line width = 2.5pt, red]
(O1) to (O2);
}$};
\node[fill=white] at (12) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
\draw[line width = 2.5pt, red]
(O1) to (I1) to (I4) (I3) to (O3);
}$};
\node[fill=white] at (111) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
\draw[line width = 2.5pt, red]
(O1) to (O2);
\draw[line width = 2.5pt, green]
(I3) to (O3) to (O4)
(O2) to (I2) to (I4) to (I1);
\node at (0,-2.5) {\tiny(no extension to a cycle)};
}$};
\node[fill=white] at (112) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
\draw[line width = 2.5pt, red]
(O1) to (O2);
\draw[line width = 2.5pt, green]
(O2) to (O3) to(O4)
(I3) to (I1) to (I4) to (I2);
\node at (0,-2.5) {\tiny(no extension to a cycle)};
}$};
\node[fill=white] at (121) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
\draw[line width = 2.5pt, red]
(O1) to (I1) to (I4) (I3) to (O3);
\draw[line width = 2.5pt, green]
(O3) to (O2) to (I2)
(I4) to (O4);
\node at (0,-2.5) {\tiny(no extension to a cycle)};
}$};
\node[fill=white] at (122) {$\TikZ{[scale=.5]\Pet
\draw[line width = 2.5pt, blue]
(O0) to (I0)
(O0) to (O1)
(I0) to (I3);
\draw[line width = 2.5pt, red]
(O1) to (I1) to (I4) (I3) to (O3);
\draw[line width = 2.5pt, green]
(O3) to (O4)
(I4) to (I2) to (O2);
\node at (0,-2.5) {\tiny(no extension to a cycle)};
}$};
}$$
\end{ans}
\item For each of the following, decide whether Dirac's theorem applies, whether Ore's theorem applies, and whether the graph has a Hamilton cycle.
$$
\text{(i)}~\begin{matrix}\begin{tikzpicture}[scale=1.5]
\node[bV] (a) at (0,0){};
\node[bV] (b) at (1,0){};
\node[bV] (c) at (1,1){};
\node[bV] (d) at (.5,1.5){};
\node[bV] (e) at (0,1){};
\draw (a) to (b) to (c) to (d) to (e) to (a) (c) to (e);
\end{tikzpicture}\end{matrix}
\qquad \qquad
\text{(ii)}~
\begin{matrix}\begin{tikzpicture}[scale=1.5]
\node[bV] (a) at (0,0){};
\node[bV] (b) at (1,0){};
\node[bV] (c) at (1,1){};
\node[bV] (d) at (.5,1.5){};
\node[bV] (e) at (0,1){};
\draw (a) to (b) to (c) to (d) to (e) to (a) (c) to (e) to (b);
\end{tikzpicture}\end{matrix}
\qquad\qquad
\text{(iii)}~\begin{matrix}\begin{tikzpicture}[scale=1.5]
\node[bV] (a) at (0,0){};
\node[bV] (b) at (1,0){};
\node[bV] (c) at (1,1){};
\node[bV] (e) at (.5,.5){};
\node[bV] (d) at (0,1){};
\draw (a) to (b) to (c) to (d) to (a) to (c) (d) to (b);
\end{tikzpicture}\end{matrix}
\qquad \qquad
\text{(iv)}~
\begin{matrix}\begin{tikzpicture}[scale=1.5]
\node[bV] (a) at (0,0){};
\node[bV] (b) at (1,0){};
\node[bV] (c) at (1,1){};
\node[bV] (e) at (.5,.75){};
\node[bV] (f) at (.5,.25){};
\node[bV] (d) at (0,1){};
\draw (a) to (b) to (c) to (d) to (a) to (f) to (b) (c) to (e) to (d) (e) to (f);
\end{tikzpicture}\end{matrix}
$$
\begin{ans}
\end{ans}
\item Give an example of a simple graph with at least 3 vertices that satisfies (1) the degree of every vertex is at least $(|V|-1)/2$, but (2) does not have a Hamilton circuit. (This shows that that Dirac's bound is ``sharp''.)
\begin{ans}If the minimum degree $\delta$ is greater or equal to $(|V|-1)/2$, then since it's an integer, is greater or equal to $\lceil (|V|-1)/2 \rceil$. Namely, if $|V|$ is even, then $\lceil (|V|-1)/2 \rceil = |V|/2$, in which case Dirac's bound applies. So we'll need to go looking for an example where $|V|$ is odd. Let's try $|V| = 3$.
If $|V| = 3$, then $(|V|-1)/2 = 1$. And the graph
$$\TikZ{
\foreach \x in {1,2,3}{\node[bV] (\x) at (\x,0){};}
\draw (1) to (2) to (3);
}$$
has three vertices, with minimum degree 1, but \emph{no} cycles (and hence no Hamilton cycle).
If you find this unsatisfying, consider the bowtie, whose minimum degree is $2 = (5-1)/2$, but doesn't have a Hamilton cycle either:
$$\TikZ{[yscale=.5, xscale=.75]
\node[bV] (1) at (0,1){};
\node[bV] (2) at (0,-1){};
\node[bV] (3) at (1,0){};
\node[bV] (4) at (2,1){};
\node[bV] (5) at (2,-1){};
\draw (1) to (2) to (3) to (4) to (5) to (3) to (1);
}$$
\end{ans}
\end{enumerate}
\end{try}
\end{document}