\documentclass[12pt,
               a4paper,
               article,
               oneside,
               oldfontcommands,
               UKenglish]{memoir}


\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[scaled]{beramono}
\usepackage[final]{microtype}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{thmtools}
\usepackage{babel}
\usepackage{csquotes}
\usepackage[nodayofweek]{datetime}
\usepackage{listings}
\lstset{basicstyle = \ttfamily}
\usepackage{textcomp}
\usepackage{siunitx}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage[colorlinks, allcolors = uiolink]{hyperref}


\renewcommand*{\chaptitlefont}{\Large\bfseries\sffamily\raggedright}
\setsecheadstyle{\large\bfseries\sffamily\raggedright}
\setsubsecheadstyle{\large\bfseries\sffamily\raggedright}
\setsubsubsecheadstyle{\normalsize\bfseries\sffamily\raggedright}
\setparaheadstyle{\normalsize\bfseries\sffamily\raggedright}
\setsubparaheadstyle{\normalsize\bfseries\sffamily\raggedright}
\setbeforesubsubsecskip{2ex}
\setaftersubsubsecskip{1ex}


\pretolerance = 2000
\tolerance    = 6000
\hbadness     = 6000


\renewcommand{\sfdefault}{phv}
\definecolor{uiolink}{HTML}{0B5A9D}


\declaretheorem[style = definition]{problem}
\declaretheorem[style = definition, sibling = problem]{exercise}


\begin{document}


\begin{titlingpage}
    \vspace*{-8em}
    \setlength{\parskip}{1.5ex plus 0.5ex minus 0.2ex}
    \setlength{\parindent}{0pt}

    \begin{flushright}
        \small\today
    \end{flushright}

    \begin{center}
        \vspace{2em}
        {
            \bfseries\sffamily\huge
            MAT2250 Discrete Mathematics
        }
        \vskip0.2ex
        \Large
        Mandatory assignment 1 of 1
        \vskip1ex
    \end{center}

    \subsubsection*{Submission deadline}
    April 2 \textsuperscript{nd} of March  2020, 14:30 in Canvas    (\href{https://canvas.uio.no}{\underline{canvas.uio.no}}).
    
    (\textbf{Changed from}    Thursday 26 \textsuperscript{th} of March  2020) 


    \subsubsection*{Instructions}
    You can choose between scanning handwritten notes or typing the solution directly on a computer (for instance with \LaTeX).
    The assignment must be submitted as a single PDF file.
    Scanned pages must be clearly legible.
    The submission must contain your name, course and assignment number.

    It is expected that you give a clear presentation with all necessary explanations.
    Remember to include all relevant plots and figures.
    Students who fail the assignment, but have made a genuine effort at solving the exercises, are given a second attempt at revising their answers.
    All aids, including collaboration, are allowed, but the submission must be written by you and reflect your understanding of the subject.
    If we doubt that you have understood the content you have handed in, we may request that you give an oral account.

    In exercises where you are asked to write a computer program, you need to hand in the code along with the rest of the assignment.
    It is important that the submitted program contains a trial run, so that it is easy to see the result of the code.

    \subsubsection*{Application for postponed delivery}
    If you need to apply for a postponement of the submission deadline due to illness or other reasons, you have to contact the Student Administration at the Department of Mathematics (e-mail: \href{mailto:studieinfo@math.uio.no}{studieinfo@math.uio.no}) well before the deadline.

    All mandatory assignments in this course must be approved in the same semester, before you are allowed to take the final examination.

    \subsubsection*{Complete guidelines about delivery of mandatory assignments:}
    \unskip
    \begin{center}
        %\unskip
        \href{http://www.uio.no/english/studies/admin/compulsory-activities/mn-math-mandatory.html}
        {
            \resizebox{\textwidth}{!}
            {\underline{uio.no/english/studies/admin/compulsory-activities/mn-math-mandatory.html}}
        }
%        \vspace{1ex}
      %  \vfill
        GOOD LUCK!
    \end{center}
\end{titlingpage}


\noindent

\begin{problem}

Let $K_n$ be the complete graph on $n$ vertices $\{v_1, \dots, v_n\}$. 


\begin{enumerate}
%\ \\ 

\item How many spanning trees are there of $K_6$ which contain a single vertex of degree $5$? Is there a spanning tree of $K_6$ with vertex degree sequence $(3, 3, 2, 1, 1, 1)$?  



\item  Let $d_1, \dots, d_n$ be a sequence of natural numbers each greater than or equal to $1$ with 
$\sum_{i = 1}^n d_i = 2n-2$. 
Show that the number of spanning trees in $K_n$ in which $\deg(v_i ) = d_i$ for all $i$  is equal to 
$$\frac{(n-2)!}{(d_1 - 1)! \dots (d_n-1)!}$$
Hint: Adapt the bijection constructed in the lectures  between spanning trees and sequences. 


\item 

Consider  the multivariable generating function where the sum is over all spanning trees  $T$ of $K_n$
$$\bold{T}(z_1, \dots , z_n)  = \sum_{T} \prod_{i= 1}^n z_i^{\deg(v_i) - 1}.$$
By the above exercise we have 
$$\bold{T}(z_1, \dots , z_n)   = \sum_{d_1, \dots , d_n} 
\frac{(n-2)!}{(d_1 - 1)! \dots (d_n-1)!}z_1^{d_1- 1} \dots z_n^{d_n-1},$$
where the sum is over all sequences of natural numbers   $d_1, \dots, d_n$ which are greater than or equal to $1$ satisfying $  \sum_{i = 1}^n d_i = 2n-2$.

Prove that $\bold{T}(z_1, \dots, z_n) = (z_1 + \dots + z_n)^{n-2}$
 for all $n$. 


\end{enumerate}

 
Deduce   the result proved in the lectures that the number of spanning trees of $K_n$ is equal to $n^{n-2}$. 
\end{problem}

\begin{problem}

Let $G = (V, E) $ be a graph with $|V| = n$. A map $f: V \to \{1, \dots , t\}$ is called an admissible vertex labeling if 
$f(v) \neq f(v')$ whenever $vv'$ is an edge of $G$. 
Let $P_G(t)$ denote the number of admissible vertex labelings of a graph $G$ with $t$ colours. 


\begin{enumerate}
\item 
Calculate $P_G(t)$ for the path $P_n$ with $n$ vertices,  the circuit $C_n$ with $n$ vertices, and  the the complete graph $K_n$.

\item For a graph $G = (V, E) $ and an edge $k \in E$, let $G \backslash k = (V, E\backslash k)$ 
and let $G / k$ denote the graph  obtained from $G$ by contracting the edge $k = uv$ and identifying the vertices $u$ and $v$.\footnote{Notice that this operation might produce loops or multiple edges. If $G$ has a loop then $P_G(t) = 0$ and it has multiple edges then $P_G(t) = P_{G'}(t)$ where $G'$ is the graph with all but one of the multiple edges removed.  }
Prove that $$P_G(t) = P_{G \backslash k} (t) - P_{G / k }(t). $$ 

Conclude from the above exercise that $P_G(t)$ is a polynomial in $t$ for all $G$. 



\item 
If $G$ is the graph with $n$ vertices and no edges then $P_G(t) = t^n$. Using this and the  above formula, show that $P_G(t)$ has degree $n= |V|$ and the leading coefficient is $1$. 

\end{enumerate}

\end{problem}


\begin{problem}
\begin{enumerate}

\item Let $T = \{1, 2, \dots, 4\}$. Find the number of distinct  transversals  (or selection functions) of the family of sets  $$\mathcal{A} = \{ \{1, 2\}, \{2, 3\}, \{3, 4\}, \{4, 1\}\}.$$ 

\item Suppose a bipartite graph $G = (S +T, E)$ is $k$-regular for $k \geq 1$  (i.e.~$\deg(u) = k$ for  all $u \in S \cup T$). Show that $|S| = |T|$ and $G$ always contains a matching $M$ with $|M| = |S| = |T|$. 

\item Show that a $k$-regular bipartite graph $G = (S + T, E)$ contains at least $k!$ matchings with $|S| = |T|$ number of edges. 

Hint: Perform induction on $n = |S| = |T|$ and see Exercise 8.28 of Aigner. 

\end{enumerate}

\end{problem}



\end{document}