
\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 7}
\end{center}



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

\item Solve all problems.
\end{itemize}


\noindent{\bf 1.} Let $1\leq d_1\leq ...\leq d_n$ be integers. Prove that there exists a tree with degrees $d_1,...,d_n$ if and only if $\sum_{i=1}^n d_i=2n-2$.

\bigskip

\noindent{\bf 2.} Given a tree $T$ and two vertices $x,y$ of $T$, let $d(x,y)$ be the length of the unique path in $T$ between $x$ and $y$.
Determine those trees $T$ on $n$ vertices for which $$\sum_{x,y\in V(T)} d(x,y)$$ is maximal and minimal, respectively.

\bigskip

\noindent{\bf 3.} Show that any tree has more leaves than vertices of degree at least 3.


\bigskip

\noindent{\bf 4.} 
Let $n=2k$. Characterize all interesting families $\mathcal{F}\subseteq \binom{[n]}{k}$ with $|\mathcal{F}|=\binom{n-1}{k-1}$.





\end{document}
