\magnification=\magstephalf \voffset=-.25truein \vsize=9.6truein
%\hoffset=-.5truein \hsize=7.28truein
%\baselineskip=10.4truept
%\lineskiplimit=0pt
%\lineskip=0pt
\nopagenumbers
\parskip=1pt
\centerline{HOMEWORK SET \#8 / CO1A / Spring 2014} \vskip8mm

\item{1.} Find the labeled tree on 9 vertices (with labels: 1
through 9) with Pr\"ufer code 6,2,2,6,2,9,9,9
\item{2.} Show that a graph $G$ is a tree if and only if \hfill\break
\null\hskip 4 em it is
cycle-free, but adding any edge to $G$  will create a cycle.
\item{3.}Prove that in every tree on $n$
vertices there are at least ${2n+2\over 3}$ vertices of degree
less than four. For every $n=3k+2$ give a tree where the number
of vertices of degree less than four is exactly  ${2n+2\over
3}=2k+2$.
\item{4.} Show that in a connected graph every two maximum (length) paths
have a common vertex.

\item{5.} Prove that if $d(x)\ge 3$ for all $x\in V(G)$ then $G$
contains a cycle of even length.
\item{6.} Prove that a graph has at least ${\chi(G) \choose 2}$
edges.
\item{7.} Prove that for any graph $G$ on $n$ vertices
$\chi(G)\chi(\overline G)\ge n$ holds.
\item{8.} Prove that for any graph $G$ on $n$ vertices $\chi(G) + \chi(\overline G)\le n+1$ holds.

\vfill\vfill \vfill\vfill \vfill\vfill


\centerline{HOMEWORK SET \#8 / CO1A / Spring 2014} \vskip8mm

\item{1.} Find the labeled tree on 9 vertices (with labels: 1
through 9) with Pr\"ufer code 6,2,2,6,2,9,9,9
\item{2.} Show that a graph $G$ is a tree if and only if \hfill\break
\null\hskip 4 em it is
cycle-free, but adding any edge to $G$  will create a cycle.
\item{3.}Prove that in every tree on $n$
vertices there are at least ${2n+2\over 3}$ vertices of degree
less than four. For every $n=3k+2$ give a tree where the number
of vertices of degree less than four is exactly  ${2n+2\over
3}=2k+2$.
\item{4.} Show that in a connected graph every two maximum (length) paths
have a common vertex.

\item{5.} Prove that if $d(x)\ge 3$ for all $x\in V(G)$ then $G$
contains a cycle of even length.
\item{6.} Prove that a graph has at least ${\chi(G) \choose 2}$
edges.
\item{7.} Prove that for any graph $G$ on $n$ vertices
$\chi(G)\chi(\overline G)\ge n$ holds.
\item{8.} Prove that for any graph $G$ on $n$ vertices $\chi(G) + \chi(\overline G)\le n+1$ holds.

\bye
