\magnification=\magstep1 

%\hsize=7.28truein
%\baselineskip=10.4truept
\nopagenumbers
\parskip=6pt
\centerline{HOMEWORK SET \#8 / CO1A / Spring 2020} \vskip5mm

\item{1.}  Find the number of non-isomorphic
connected, unicyclic graphs (graphs with exactly one cycle) on 6
vertices (a bit boring, but useful).

\item{2.} Prove that a graph $G$ contains a circuit of length at
least  $k+1$ if $d(x)\ge k$ for all $x\in V(G)$.

\item{3.} Show that the complement of a disconnected graph is connected!

\item{4.} Determine all graphs with exactly one pair of vertices
of equal degree (all other degrees are distinct).

\item{5.} For every $n \ge 3$ give an example of a graph $G$
having $\chi(G) \ge n$ but $G \not\supseteq K_n$.


\item{6.} Prove that for every graph $G$ on the vertex set $V$
there is a partition of $V=V_1\cup V_2$ such that if $G(V_1)$ and
$G(V_2)$ denote the graphs spanned by $G$ on the sets $V_1$ and
$V_2$ respectively, than $\chi(G(V_1))+\chi(G(V_2))=\chi(G)$.

\item{7.} Prove that a graph has at least ${\chi(G) \choose 2}$ edges.
\item{8.} Prove that for any graph $G$ on $n$ vertices
$\chi(G)\chi(\overline G)\ge n$ holds.


 \bye
