% Homework 7 solutions, CSCE 235, spring 2007
% Assigned 10 April 2007; due 20 April 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=8.5truein
\pdfhorigin=1.5truein \pdfvorigin=1.25truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\N{\mathord{\bf N}}  \def\Z{\mathord{\bf Z}}
\def\Q{\mathord{\bf Q}}  \def\R{\mathord{\bf R}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Homework assignment~7} (solutions)}
\centerline{Assigned Tuesday, April~10, 2007}
\centerline{Due Friday, April~20, 2007}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (18~points) Make a list of drawings of all the simple graphs with at
most four vertices. The list should not contain any isomorphic pairs of graphs.
(You should get a list of 18~graphs.)

\solution
{
\def\row{height10pt&\omit&\omit&&\omit&\omit&&\omit&\omit&\cr
\noalign{\hrule}
height10pt&\omit&\omit&&\omit&\omit&&\omit&\omit&\cr}
$$\vbox{\offinterlineskip
\hrule
\halign{&\vrule#&\strut\quad\hfil#\quad&\hfil\midfig{homework-7-sol.#}\hfil\quad\cr
height10pt&\omit&\omit&&\omit&\omit&&\omit&\omit&\cr
	&1.&7&&2.&8&&3.&9&\cr
\row
	&4.&10&&5.&11&&6.&12&\cr
\row
	&7.&13&&8.&14&&9.&15&\cr
\row
	&10.&16&&11.&17&&12.&18&\cr
\row
	&13.&19&&14.&20&&15.&21&\cr
\row
	&16.&22&&17.&23&&18.&24&\cr
height10pt&\omit&\omit&&\omit&\omit&&\omit&\omit&\cr}
\hrule}$$
}  % end \def\row

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (8~points) Draw a graph with exactly five vertices, each of degree~5,
or explain why such a graph does not exist.

\solution No such graph exists, because by the handshaking theorem (i.e., the
degree-sum theorem, page~599), the number of vertices in a graph which have
odd degree must be even.

Note that it is {\it not\/} a rigorous argument to begin with the complete
graph on five vertices, say that each vertex has degree~4, and argue that there
is no way to add more edges to bring all the degrees up to~5. For one thing,
this argument makes the assumption that the only way it would be possible to
make a graph with exactly five vertices each of degree~5 is to start
with~$K_5$, but there is no justification for this assertion. Conceivably, a
graph with exactly five vertices each of degree~5 may not have $K_5$ as a
subgraph. The handshaking theorem is required for a rigorous justification for
this problem.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Draw $Q_4$. Is this graph bipartite?

\solution $Q_4$ is the graph whose vertices are labeled with all possible bit
strings of length~4, in which two vertices are connected by an edge if and
only~if their labels differ in exactly one position. There are many ways to
draw this graph. One way is shown below.

$$\fig{homework-7-sol.25}$$

\noindent Note that in this drawing, each of the positions of the bit string
has a ``meaning.'' The first bit is 0 for those vertices in the outer ring and
1 for those vertices in the inner ring. The second bit is 0 for those vertices
at the four main compass points (north, south, east, and west), and 1 for the
vertices in between (northeast, southeast, northwest, and southwest). The third
bit is 0 for the vertices to the right of a line that goes through the center
of the drawing and through the compass points NNW and~SSE, and 1 for the
vertices to the left of this line. Finally, the fourth bit is 0 for the
vertices above a line that passes through the center of the drawing and through
the compass points ENE and~WSW, and 1 for the vertices below this line. The
symmetry of the drawing above is due in part to this arrangement of the
vertices, so that each bit has a meaningful interpretation.

This graph is bipartite, as are all $n$-cubes. To see this, let $A$ be the set
of vertices in~$Q_4$ whose labels contain an even number of~1s, and let $B$ be
the set of vertices in~$Q_4$ whose labels contain an odd number of~1s. Clearly
every vertex in~$Q_4$ is in either $A$ or~$B$, and no vertex is in both $A$
and~$B$, so $A$ and~$B$ form a partition of the vertex set of~$Q_4$. Since
every edge in the graph connects two vertices that differ in exactly one
position, every edge connects a vertex with an even number of~1s to a vertex
with an odd number of~1s. In other words, there is no edge that connects a
vertex in~$A$ to another vertex in~$A$, and there is no edge that connects a
vertex in~$B$ to another vertex in~$B$. Thus the pair~$(A,B)$ is a bipartition
of the vertex set of~$Q_4$, and hence $Q_4$ is bipartite.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (24~points) For each of the graphs below, determine whether it has an
Euler circuit, and construct such a circuit if one exists. If the graph has no
Euler circuit, explain why. Also determine whether the graph has a Hamiltonian
circuit, and either construct such a circuit if one exists or justify your
claim that there is no Hamiltonian circuit.

$$\matrix{
	\hbox{(a)}&\midfig{homework-7-sol.1}&\hskip1in&\hbox{(c)}&\midfig{homework-7-sol.3}\cr
\noalign{\vskip0.3in}
	\hbox{(b)}&\midfig{homework-7-sol.2}&&\hbox{(d)}&\midfig{homework-7-sol.4}\cr
}$$

\solution
\part{(a)} Since the degree of every vertex is even, this graph has an Euler
circuit; one such circuit is $a$,~$c$, $e$, $b$, $c$, $d$,~$a$. However, it
does not have a Hamiltonian circuit. Such a circuit would need to include~$a$
at some point, then later travel to~$b$, and eventually come back to~$a$. This
requires visiting $c$ twice.

\part{(b)} This graph has no Euler circuit, since the vertex~$b$ has degree~3,
which is odd. It does have a Hamiltonian circuit, for example, $a$,~$e$, $d$,
$f$, $c$, $b$,~$a$.

\part{(c)} Since the degree of every vertex is even, this graph has an Euler
circuit, for example, $a$,~$b$, $c$, $d$, $e$, $a$, $c$, $e$, $b$, $d$,~$a$. It
also has a Hamiltonian circuit, for example, $a$,~$b$, $c$, $d$, $e$,~$a$.

\part{(d)} Again, since the degree of every vertex is even, this graph has an
Euler circuit, for example, $a$,~$c$, $d$, $a$, $g$, $e$, $d$, $g$, $f$, $b$,
$d$, $f$,~$a$. However, it does not have a Hamiltonian circuit. In order for a
Hamiltonian circuit in this graph to reach the vertex~$b$, for example, it
would need to pass through~$d$ either immediately before~$b$ or immediately
after. The same goes for the vertices $c$ and~$e$. But a Hamiltonian circuit
can visit~$d$ only once, so it cannot visit all three of $b$,~$c$, and~$e$.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (12~points) In graph models of saturated hydrocarbons, each carbon
atom is represented by a vertex of degree~4, and each hydrogen atom is
represented by a vertex of degree~1. (See Example~5 on page~688 of the
textbook.) The nonisomorphic trees with $n$~vertices of degree~4 and
$2n+2$~vertices of degree~1 represent the different isomers of ${\rm C}_n{\rm
H}_{2n+2}$. How many isomers are there of
\smallskip
\item{(a)} propane ($\rm C_3H_8$)?
\item{(b)} pentane ($\rm C_5H_{12}$)?
\item{(c)} hexane ($\rm C_6H_{14}$)?

\solution It turns out that we can ignore the hydrogen atoms when we draw the
molecules; the only thing that matters is the arrangement of the carbon atoms.

\part{(a)} Propane, $\rm C_3H_8$, has just one isomer, shown below.
$$\fig{homework-7-sol.26}$$

\part{(b)} Pentane, $\rm C_5H_{12}$, has three isomers, shown below.
$$\vbox{\offinterlineskip
\halign{\hfil\midfig{homework-7-sol.#}\hfil&\qquad#\hfil\cr
	27&$n$-pentane\cr
\noalign{\vskip10pt}
	28&isopentane (methylbutane)\cr
\noalign{\vskip10pt}
	29&neopentane (dimethylpropane)\cr
}}$$

\part{(c)} Hexane, $\rm C_6H_{14}$, has five isomers, shown below.
$$\vbox{\offinterlineskip
\halign{\hfil\midfig{homework-7-sol.#}\hfil&\qquad#\hfil\cr
	30&$n$-hexane\cr
\noalign{\vskip10pt}
	31&isohexane (2-methylpentane)\cr
\noalign{\vskip10pt}
	32&3-methylpentane\cr
\noalign{\vskip10pt}
	33&2,3-dimethylbutane\cr
\noalign{\vskip10pt}
	34&neohexane (2,2-dimethylbutane)\cr
}}$$

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Build a binary search tree for the words in the sentence
``now is the time for all good men to come to the aid of their party'',
inserting the words into the tree in the order they appear in the sentence. Do
not insert duplicate words more than once.

\solution
$$\fig{homework-7-sol.35}$$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (21~points) Consider the following tree~$T$.
$$\fig{homework-7-sol.5}$$
Form an ordered rooted tree~$T'$ from~$T$ by choosing $d$ as the root and
ordering the children of each internal vertex alphabetically. Draw~$T'$. In
what order are the vertices encountered in the preorder traversal of~$T'$? in
the inorder traversal of~$T'$? in the postorder traversal of~$T'$? Answer the
same questions if $j$ is chosen as the root, and if $f$ is chosen as the root.

\solution We begin by choosing $d$ to be the root. The resulting ordered rooted
tree~$T'$ is shown below.
$$\fig{homework-7-sol.36}$$
The preorder traversal will visit the vertices of~$T'$ in the order $d$,~$c$,
$a$, $b$, $e$, $f$, $g$, $j$, $i$, $h$, $l$, $k$,~$m$. The inorder traversal
will visit the vertices in the order $a$,~$c$, $b$, $d$, $f$, $e$, $g$, $h$,
$i$, $j$, $k$, $l$,~$m$. The postorder traversal will visit the vertices in the
order $a$,~$b$, $c$, $f$, $g$, $e$, $h$, $i$, $k$, $m$, $l$, $j$,~$d$.

\vfill\eject

\noindent We now choose $j$ to be the root, and we obtain the ordered rooted
tree below.
$$\fig{homework-7-sol.37}$$
The preorder traversal of this tree will visit the vertices in the order
$j$,~$d$, $c$, $a$, $b$, $e$, $f$, $g$, $i$, $h$, $l$, $k$,~$m$. The inorder
traversal will visit the vertices in the order $a$,~$c$, $b$, $d$, $f$, $e$,
$g$, $j$, $h$, $i$, $k$, $l$,~$m$. The postorder traversal will visit the
vertices in the order $a$,~$b$, $c$, $f$, $g$, $e$, $d$, $h$, $i$, $k$, $m$,
$l$,~$j$.

If we choose $f$ as the root, we get the following ordered rooted tree.
$$\fig{homework-7-sol.38}$$
The preorder traversal of this tree will visit the vertices in the order
$f$,~$e$, $d$, $c$, $a$, $b$, $j$, $i$, $h$, $l$, $k$, $m$,~$g$. The inorder
traversal will visit the vertices in the order $a$,~$c$, $b$, $d$, $h$, $i$,
$j$, $k$, $l$, $m$, $e$, $g$, $f$. The postorder traversal will visit the
vertices in the order $a$,~$b$, $c$, $h$, $i$, $k$, $m$, $l$, $j$, $d$, $g$,
$e$,~$f$.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (12~points) Find a spanning tree for the graph shown below by
beginning at~$a$ and using
\smallskip
\item{(a)} depth-first search.
\item{(b)} breadth-first search.
$$\fig{homework-7-sol.6}$$

\solution
\part{(a)} One possible answer is shown below. The numbers on the edges do
{\it not\/} indicate weights; rather, they indicate the order in which the
edges are added to the spanning tree as it is being built.
$$\fig{homework-7-sol.39}$$

\part{(b)} One possible answer is shown below. Again, the numbers on the edges
do not indicate weights; rather, they indicate the order in which the edges are
added to the spanning tree as it is being built. With breadth-first search, it
is often helpful to imagine whole sets of edges being added at once, which is
why three edges are labeled with~1 and the other three are labeled with~2.
$$\fig{homework-7-sol.40}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye