\magnification=\magstep1 \voffset=-.35truein \advance\vsize
1.56truein \hoffset=-.25truein
%\hsize=7.28truein
%\baselineskip=10.4truept
\nopagenumbers
%\parskip=1pt
\centerline{HOMEWORK SET \#9 / CO1A / Spring 2020} \vskip3mm
\item{1.}  Give an example of a graph $G$ with $\chi(G)=2$ and a
coloring of $G$ with the greedy algorithm (that is an ordering of
the vertices of $G$ in which order the greedy algorithm colors the
vertices of the graph) requiring $n$ colors (for every $n$ big
enough)
\item{2.}  Prove that for any graph $G$ on $n$ vertices $\chi(G) + \chi(\overline G)\le n+1$ holds.
\item{3.} What can be the chromatic number of a connected
simple graph with exactly two cycles?

\item{4.} 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{5.} 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{6.} Show that in a connected graph every two maximum (length) paths
have a common vertex.
\item{7.}  Find the labeled tree on 9 vertices (with labels: 1
through 9) with Pr\"ufer code 6,2,1,6,2,9,8.
\item{8.} Show that for every sequence $1 \le d_1 \le d_2 \le \cdots \le d_n$ with $n \le \sum_{i=1}^n d_i \le 2n-2$,  $2\big\vert \sum_{i=1}^n d_i$ there is a forest with  this sequence as degree sequence. Is this forest unique (up to isomorphism)?



 \bye
