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



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



\noindent{\bf 1.} 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 2.} Show that any tree has more leaves than vertices of degree at least 3.


\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.} Calculate $ST(K_{n,m})$, i.e., the number of spanning trees of the complete bipartite graph $K_{n,m}$.


\bigskip

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

\bigskip

\noindent{\bf 6.}
Let $n>2k$ and $\mathcal{F}$ be an intersecting family in $\binom{[n]}{k}$ of size $\binom{n-1}{k-1}$.
Following the notation given in class, prove that if $\mathcal{F}_\pi=\{A_1, A_2,...,A_k\}$ for some cyclic permutation $\pi$, then $|A_1\cap A_2\cap ...\cap A_k|=1$ and $|A_1\cup A_2\cup ...\cup A_k|=2k-1$.


\end{document}
