
\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, 2020 Fall, USTC} \\
    {Homework 5}
\end{center}



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

\noindent{\bf 1.}
Let $G$ be a graph such that for any two non-adjacent vertices $u,v$, it holds that $N_G(u)=N_G(v)$. Prove that $G$ must be a {\it complete multipartite graph}
(i.e., $V(G)$ can be partitioned into $V_1, V_2,...,V_k$ for some $k\ge 2$ such that for any $u\in V_i, v\in V_j$ where $i\neq j$, we have $uv\in E(G)$).

\bigskip

\noindent{\bf 2.} 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 3.} Show that if a graph $G$ on $n$ vertices does not contain $K_{s,t}$ as a subgraph, then it has at most $C\cdot n^{2-1/s}$ edges for some absolute constant $C$ only depending on $t$ and $s$.


\bigskip

\noindent{\bf 4.} 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 5.} For all 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 6.} 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}

\end{document}
