
\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{mathrsfs}
\addtolength{\topmargin}{-.5in} \addtolength{\textheight}{1in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\evensidemargin}{-.6in} \addtolength{\textwidth}{1.2in}
\usepackage{latexsym,amsmath,amssymb,amsfonts,epsfig,graphicx,cite,psfrag}
\usepackage{eepic,color,colordvi,amscd}


\def\qed{\hfill \rule{4pt}{7pt}}

\def\pf{\noindent {\it Proof. }}




\pagestyle{plain}


\begin{document}
\begin{center}
    \large{Combinatorics, 2016 Fall, USTC} \\
    {Homework 6}
\end{center}



\begin{itemize}
\item The due is on Tuesday, Nov. 1, at beginning of the class.

\item Solve all problems.
\end{itemize}


\noindent{\bf 1.} Let $L$ be a set of $n$ distinct lines in the plane and $P$ a set of $n$ distinct points in the plane. 
Prove that the number of pairs $(p,\ell)$, where $p\in P,~\ell\in L$, and $p$ lies on $\ell$, is bounded from above by $O(n^{3/2})$. 


\bigskip

\noindent{\bf 2.} Let $t_n=ST(K_n)$. Prove the following recurrent formula $$(n-1)t_n=\sum_{k=1}^{n-1} k(n-k)\binom{n-1}{k-1}t_kt_{n-k}.$$

\bigskip

\noindent{\bf 3.} Given a graph $G$ on $n$ vertices, let $Q$ be its Laplace matrix, and let $Q^*$ be the matrix whose element at position $(i,j)$ equals $(-1)^{i+j} \det Q_{ij}$.
Prove the following:
\begin{itemize}
\item[(1).] $\det Q=0$.
\item[(2).] If $G$ is connected, then $Q$ has rank $n-1$.
\item[(3).] If $G$ is disconnected, then the rank of $Q$ is at most $n-2$.
\item[(4).] If $G$ is connected and $\vec{x}\in R^n$ is an arbitrary vector, then $Q\vec{x}=\vec{0}$ if and only if $\vec{x}$ is a multiple of the vector $\vec{1}=(1,1,...,1)^T$.
\item[(5).] Show that $Q Q^*$ is a zero matrix. Using (4), infer that $Q^*$ is an identical matrix.
\end{itemize}


\bigskip

\noindent{\bf 4.} For all values of positive integers $n$, determine the number of spanning trees on given $n$ vertices in which all vertices have degree 1, 2, or 3.


\bigskip

\noindent{\bf 5.} For each $1\le k\le n-1$, let $N_k$ denote the number of spanning trees of $K_n$ in which the vertex $n$ has degree $k$. (Here we assume that $V(K_n)=\{1,2,...,n\}$.)
\begin{itemize}
\item [(a)] Prove that $(n-1-k)N_k=k(n-1)N_{k+1}$. 
\item [(b)] Prove by induction on $k$ that $N_k=\binom{n-2}{k-1} (n-1)^{n-1-k}$.
\item [(c)] Use the above equality to derive the Cayley's formula.
\end{itemize}

\bigskip

\noindent{\bf 6.} Let $D$ be a digraph defined on the vertex set $[n]$ such that every vertex has out-degree one. 
Prove that each component of such a digraph is a directed cycle, possibly with some trees hanging at the vertices of the cycle, with edges directed towards the cycle.
Then use this to show that the mapping $\varphi: \mathcal{D}\to \mathcal{V}$ defined in the class indeed is a bijection.  





\bigskip

\noindent{\bf 7.} Calculate $ST(K_{n,m})$, i.e., the number of spanning trees of the complete bipartite graph $K_{n,m}$.





\end{document}
