\filename{ma251bex.tex}
\versiondate{16.2.95}
\def\qnAA{(a) For $n\ge 0$, find $\sum_{k=0}^n{^nC_k}$,
$\sum_{k=0}^n\sum_{j=0}^k{^kC_j}\ {^nC_k}$,
$\sum_{k=0}^n\sum_{j=0}^k\sum_{i=0}^j{^jC_i}\ {^kC_j}\ {^nC_k}$.
(b) Let $X$ be a set of size $n$. Find $\#(\Cal PX)$,
$\#(\{(b,c):b\subseteq c\subseteq X\})$,
$\#(\{(a,b,c):a\subseteq b\subseteq c\subseteq X\})$.
(c) Explain why the answers in (a) are related to those in (b).
\hfill[AA]}
\def\ansAA{(a)
\Centerline{$\sum_{k=0}^n{^nC_k}=2^n$, }
\Centerline{$\sum_{k=0}^n\sum_{j=0}^k{^kC_j}\ {^nC_k}
=\sum_{k=0}^n2^k{^nC_k}
=\sum_{k=0}^n2^k1^{n-k}{^nC_k}
=(2+1)^n=3^n$,}
\Centerline{$\sum_{k=0}^n\sum_{j=0}^k\sum_{i=0}^j{^jC_i}\ {^kC_j}\ {^nC_k}
=\sum_{k=0}^n3^k{^nC_k}
=\sum_{k=0}^n3^k1^{n-k}{^nC_k}
=(3+1)^n=4^n$.}
\medskip
(b) $\#(\Cal PX)=2^n$,
\Centerline{$\#(\{(b,c):b\subseteq c\subseteq X\})=3^n$}
\noindent because to specify $b$, $c$ we have to say, for each $x\in X$, whether it belongs to $b$, to $c\setminus b$, or to $X\setminus c$; thus we have three choices for each of $n$ different points;
\Centerline{$\#(\{(a,b,c):a\subseteq b\subseteq c\subseteq X\})=4^n$}
\noindent because now we can choose, for each $x\in X$, whether $x\in a$, $x\in b\setminus a$, $x\in c\setminus b$ or $x\in X\setminus c$.
\medskip
(c)(i) $\#(\Cal PX)=\sum_{r=0}^n\#([X]^r)=\sum_{r=0}^n{^nC_r}$ if $\#(X)=n$.
\medskip
\quad (ii)
$$\eqalign{\#(\{(b,c):b\subseteq c\subseteq X\})
&=\sum_{k=0}^n\sum_{j=0}^k\#(\{(b,c):b\subseteq c\subseteq X,\,\#(c)=k,\,\#(b)=j\})\cr
&=\sum_{k=0}^n\sum_{j=0}^k{^kC_j}\#(\{c:c\subseteq X,\,\#(c)=k\})\cr
&=\sum_{k=0}^n\sum_{j=0}^k{^kC_j}\ ^nC_k.\cr}$$
\medskip
\quad (iii)
$$\eqalign{\#(\{(a,b,c):&a\subseteq b\subseteq c\subseteq X\})\cr
&=\sum_{k=0}^n\sum_{j=0}^k\sum_{i=0}^j\#(\{(a,b,c):a\subseteq b\subseteq c\subseteq X,\,\#(c)=k,\,\#(b)=j,\,\#(a)=i\})\cr
&=\sum_{k=0}^n\sum_{j=0}^k\sum_{i=0}^j{^jC_i}\#(\{(b,c):b\subseteq c\subseteq X,\,\#(c)=k,\,\#(b)=j\})\cr
&=\sum_{k=0}^n\sum_{j=0}^k{^jC_i}\ {^kC_j}\ ^nC_k.\cr}$$
}
\def\qnAB{(a) Show that $\sum_{r=0}^nr(r-1)\ {^nC_r}=2^{n-2}n(n-1)$ for
every $n\ge 0$. ({\it Hint:} find $\#(\{(a,b):a\subseteq b\subseteq X$
and $\#(a)=2\})$, where $\#(X)=n$.)
(b) Find $\sum_{r=0}^nr^2\ {^nC_r}$ for $n\ge 0$.
(c) Show that $\sum_{r=0}^nr(r-1)(r-2)\ {^nC_r}=2^{n-3}n(n-1)(n-2)$ for
every $n\ge 0$. ({\it Hint:} find $\#(\{(a,b):a\subseteq b\subseteq X$
and $\#(a)=3\})$, where $\#(X)=n$.)
(d) Find $\sum_{r=0}^nr^3\ {^nC_r}$ for $n\ge 0$.
\hfill[AB]}
\def\ansABa{(a) Assuming for the moment that $n\ge 2$,
$$\eqalignno{\#(\{(a,b):a\subseteq b\subseteq X,\,\#(a)=2\})
&=\Bover{n(n-1)}2.2^{n-2}\cr
\noalign{\noindent (counting the number of doubleton sets $a$, which is $^nC_2=\Bover{n(n-1)}2$, and for each of them counting the number of possible $b$, which is $2^{n-2}$)}
&=\sum_{r=2}^n\#(\{(a,b):a\subseteq b\subseteq X,\,\#(a)=2,\,\#(b)=r\}\cr
&=\sum_{r=2}^n{^nC_r}\ ^rC_2\cr
\noalign{\noindent (counting the number of sets $b$ of size $r$, and for each of them counting the doubleton subsets)}
&=\sum_{r=2}^n\Bover{r(r-1)}2\ ^nC_r\cr
&=\sum_{r=0}^n\Bover{r(r-1)}2\ ^nC_r.\cr}$$
\noindent Multiplying by 2, we get
\Centerline{$\sum_{r=0}^nr(r-1)\ {^nC_r}=2^{n-2}n(n-1)$}
\noindent as required.
If $n=0$ or $n=1$ then
\Centerline{$\sum_{r=0}^nr(r-1)\ {^nC_r}=0=2^{n-2}n(n-1)$.}
\medskip
(b)
$$\eqalign{\sum_{r=0}^nr^2\ {^nC_r}
&=\sum_{r=0}^nr(r-1)\ {^nC_r}+\sum_{r=0}^nr\ {^nC_r}\cr
&=2^{n-2}n(n-1)+2^{n-1}n\cr
&=2^{n-2}n(n+1).\cr}$$
}%end of ansABa
\def\ansABc{(c) Assuming for the moment that $n\ge 3$,
$$\eqalignno{\#(\{(a,b):a\subseteq b\subseteq X,\,\#(a)=3\})
&=\Bover{n(n-1)(n-2)}6.2^{n-3}\cr
\noalign{\noindent (counting the number of triplet sets $a$, which is $^nC_3=\Bover{n(n-1)(n-2)}6$, and for each of them counting the number of possible $b$, which is $2^{n-3}$)}
&=\sum_{r=3}^n\#(\{(a,b):a\subseteq b\subseteq X,\,\#(a)=3,\,\#(b)=r\}\cr
&=\sum_{r=3}^n{^nC_r}\ ^rC_3\cr
\noalign{\noindent (counting the number of sets $b$ of size $r$, and for each of them counting the triplet subsets)}
&=\sum_{r=3}^n\Bover{r(r-1)(r-2)}6\ ^nC_r\cr
&=\sum_{r=0}^n\Bover{r(r-1)(r-2)}6\ ^nC_r.\cr}$$
\noindent Multiplying by 6, we get
\Centerline{$\sum_{r=0}^nr(r-1)(r-2)\ {^nC_r}=2^{n-3}n(n-1)(n-2)$}
\noindent as required.
If $n\le 2$ then
\Centerline{$\sum_{r=0}^nr(r-1)(r-2)\ {^nC_r}=0=2^{n-3}n(n-1)(n-2)$.}
\medskip
(d)
$$\eqalign{\sum_{r=0}^nr^3\ {^nC_r}
&=\sum_{r=0}^nr(r-1)(r-2){^nC_r}+3\sum_{r=0}^nr^2\ {^nC_r}
-2\sum_{r=0}^nr\ {^nC_r}\cr
&=2^{n-3}n(n-1)(n-2)+3.2^{n-2}n(n+1)-2.2^{n-1}n\cr
&=2^{n-3}n^2(n+3).\cr}$$
}
\def\qnAC{Suppose that $0\le j\le k\le n$ and that $X$ is a set of size
$n$. Set $R=\{(a,b):a\subseteq b\subseteq X,\,\#(a)=j,\,\#(b)=k\}$.
For $a\in[X]^j$ find $\#(\{b:(a,b)\in R\})$ and for $b\in[X]^k$ find
$\#(\{a:(a,b)\in R\})$. Hence show that
$\#(R)={^nC_k}\ {^kC_j}={^nC_j}\ {^{n-j}C_{k-j}}
={^nC_j}\ {^{n-j}C_{n-k}}$.
\hfill[AC]}
\def\ansAC{If $\#(a)=j$, then
\Centerline{$\#(\{b:a\subseteq b\subseteq X,\,\#(b)=k\})=\#(\{c:c\subseteq X\setminus a,\,\#(c)=k-j\}
=\ ^{n-j}C_{k-j}$;}
\noindent so
\Centerline{$\#(R)=\sum_a\#(\{b:(a,b)\in R\})
=\ ^nC_j\ ^{n-j}C_{k-j}=\ ^nC_j\ ^{n-j}C_{n-k}$.}
\noindent If $\#(b)=k\}$, then
\Centerline{$\#(\{a:a\subseteq b,\,\#(a)=j\})=\ ^kC_j$,}
\noindent so
\Centerline{$\#(R)=\sum_b\#(\{a:(a,b)\in R\})
=\ ^nC_k\ ^kC_{j}$.}
}
\def\qnAD{(a) For $n\ge 0$, write $q_n$ for the number of subsets of a
set of $n$ members which have size divisible by 3. Find $q_0$, $q_1$,
$q_2$, $q_3$. Show that $q_n=\bover13(2^n+2\Real(1+\omega)^n)$ for
every $n$, where $\omega=e^{2\pi i/3}$.
(b) For $n\ge 0$, write $q'_n$ for the number of subsets of a set of $n$
members which have size divisible by 4. Find $q'_0$, $q'_1$, $q'_2$,
$q'_3$. Show that $q'_n=\bover14(2^n+2\Real(1+i)^n)$ for every $n$.
\hfill[AD]}
\def\ansAD{(a) $q_0=1$, $q_1=1$, $q_2=1$, $q_3=2$. In general,
\Centerline{$\Real(1+\omega)^n
=\Real(\sum_{k=0}^n{^nC_k}\omega^k)
=\sum_{k=0}^n{^nC_k}\Real\omega^k$.}
\noindent Now if $k$ is divisible by $3$, $\Real(\omega^k)=\omega^k=1$,
while for any other $k\,\,\Real(\omega^k)=-\bover12$. So in the sum we get a contribution 1 from each set with a multiple of 3 members, and
$-\bover12$ from any other; that is, a contribution $1$ from each of $q_n$ sets, and a contribution $-\bover12$ from each of $2^n-q_n$ sets. Putting these together,
\Centerline{$\Real(1+\omega)^n=q_n-\Bover12(2^n-q_n)
=\Bover32q_n-2^{n-1}$,}
\noindent and
\Centerline{$q_n=\Bover13(2^n+2\Real(1+\omega)^n)$.}
\medskip
(b) $q'_0=q'_1=q'_2=q'_3=1$. In general,
\Centerline{$\Real(1+i)^n
=\Real(\sum_{k=0}^n\ ^nC_ki^k)
=\sum_{k=0}^n\ ^nC_k\Real i^k$.}
\noindent Now if $k$ is divisible by $4$, $\Real(i^k)=i^k=1$; if $k$ is divisible by $2$ but not by $4$, $\Real i^k=-1$; while if $k$ is odd, $\Real i^k=0$. So in the sum we get a contribution 1 from each set with a multiple of 4 members, and
$-1$ from any other set with an even number of members; that is, a contribution $1$ from each of $q'_n$ sets, and a contribution
$-1$ from each of $2^{n-1}-q'_n$ sets, because just half the sets have an even number of members. Putting these together,
\Centerline{$\Real(1+i)^n=q'_n-(2^{n-1}-q'_n)
=2q_n-2^{n-1}$,}
\noindent and
\Centerline{$q'_n=\Bover14(2^n+2\Real(1+i)^n)$.}
}
\def\qnAE{For $n\ge 0$, let $q^*_n$ be the number of subsets $a$ of a
set of size $n$ such that $\#(a)\equiv 1$ mod 3. Find $q^*_n$ for $n\le
5$. Setting $\omega=e^{2\pi i/3}$,
$\gamma_n=\Real(\Bover1{\omega}(1+\omega)^n)$, show that
$\gamma_n=\Bover32q^*_n-\Bover122^n$. Find $\gamma_7$.
\hfill[AE]}
\def\ansAE{(No answer written out.)}
\def\qnAF{For $n\ge 1$, let $s_n$ be the number of ways of putting $n$
Christmas cards into $n$ envelopes in such a way that every card is in
the wrong envelope. (a) Find $s_1$, $s_2$, $s_3$, $s_4$, $s_5$. (b)
Show that $s_{n+2}=(n+1)(s_n+s_{n+1})$ for every $n\ge 1$. (c) Set
$\alpha_n=s_n/n!$. Show that
$\alpha_{n+2}=\bover{n+1}{n+2}\alpha_{n+1}+\bover1{n+2}\alpha_n$ for
every $n\ge 1$.
(d) Show that $\alpha_n=\sum_{k=0}^n\Bover{(-1)^k}{k!}$ for each $n\ge
1$, and hence find $\lim_{n\to\infty}\alpha_n$.
\hfill[AF]}
\def\ansAF{(a) $s_1=0$, $s_2=1$, $s_3=2$, $s_4=9$, $s_5=44$.
\medskip
(b) In general, if we have $n+2$ cards, there are $n+1$ possible envelopes in which to put the first card. Now look at the card belonging to the envelope in which we put that first card. ($\alpha$) We might put it into the envelope belonging to the first card. In that case we have $n$ remaining cards to fit into envelopes, and there are $s_n$ ways of getting them all wrong. ($\beta$) If we want to do anything else, it's as if we had matched that second card to that first envelope, and declared that on that matching we had to get all the $n+1$ remaining cards wrong. So there will be $s_{n+1}$ ways of doing it.
Thus $s_{n+2}=(n+1)(s_n+s_{n+1})$.
\medskip
(c) $\alpha_{n+2}=\Bover1{(n+2)!}s_{n+2}
=\Bover1{(n+2)!}(n+1)(s_n+s_{n+1})
=\Bover1{(n+2)!}(n+1)(n!\alpha_n+(n+1)!\alpha_{n+1})
=\Bover1{n+2}\alpha_n+\Bover{n+1}{n+2}\alpha_{n+1}$.
\medskip
(d) Induce on $n$. $\alpha_1=s_1=0=1-1$, $\alpha_2=\Bover12s_2=\Bover12=1-1+\Bover12$. For the step to $n\ge 3$, we have
$$\eqalignno{\alpha_n
&=\Bover1n\alpha_{n-2}+\Bover{n-1}n\alpha_{n-1}\cr
&=\Bover1n\sum_{k=0}^{n-2}\Bover{(-1)^k}{k!}
+\Bover{n-1}n\sum_{k=0}^{n-1}\Bover{(-1)^k}{k!}\cr
\noalign{\noindent (by the inductive hypothesis)}
&=\sum_{k=0}^{n-2}\Bover{(-1)^k}{k!}
+\Bover{n-1}n\Bover{(-1)^{n-1}}{(n-1)!}\cr
&=\sum_{k=0}^{n-2}\Bover{(-1)^k}{k!}
+\Bover{(-1)^{n-1}}{(n-1)!}-\Bover{1}n\Bover{(-1)^{n-1}}{(n-1)!}\cr
&=\sum_{k=0}^{n}\Bover{(-1)^k}{k!}.\cr}$$
Consequently
\Centerline{$\lim_{n\to\infty}\alpha_n
=\sum_{k=0}^{\infty}\Bover{(-1)^k}{k!}=\exp(-1)=\Bover1e$.}
}
\def\qnAG{Show that if $n\ge 1$, $k\ge 0$ then the number of strings $(m_1,\ldots,m_n)$ of non-negative integers such that $m_1+\ldots+m_n=k$ is just $^{k+n-1}C_k$.
\hfill[AG]}
\def\ansAG{(No answer written out.)}
\def\qnAH{Show that if $m\ge n\ge 1$ then
$\sum_{i=n}^{m}\ ^{i-1}C_{i-n}=\ ^mC_n$. ({\it Hint:} show that
$^{i-1}C_{i-n}=\#(\{a:a\subseteq\{1,\ldots,m\},\,\#(a)=n,\,\max a=i\})$.)
\hfill[AH]}
\def\ansAH{(No answer written out.)}
\def\qnBA{Let $G=(V,E)$ be a graph. (a) What is meant by
(i) the {\it order} of $G$
(ii) the {\it complement} $\overline{G}$ of $G$
(iii) a {\it path} in $G$
(iv) a {\it simple path} in $G$
(v) a {\it closed path} in $G$
(vi) a {\it cycle} in $G$
(vii) a {\it component} of $G$
(viii) saying that $G$ is {\it connected}
(ix) the {\it degree} $d(v)$ of a vertex $v$ of $G$
(x) saying that $G$ is a {\it tree}.
(b) Show that if $V\ne\emptyset$ and $d(v)\ge 2$ for every $v\in V$, then $G$ has a
cycle.
(c) Show that $\sum_{v\in V}d(v)=2\#(E)$.
(d) Show that if $V\ne\emptyset$ and $G$ has no cycle then $\#(E)<\#(V)$.
(e) Show that if $G$ is connected then $\#(E)\ge\#(V)-1$.
(f) Show that if $V\ne\emptyset$ then the following are equivalent: (i) $G$ is a tree; (ii) $G$
is connected and $\#(V)\ge\#(E)+1$; (iii) $G$ has no cycle and
$\#(V)\le\#(E)+1$.
\hfill[BA]}
\def\ansBAa{(a)(i) The {\bf order} of $G$ is $\#(V)$.
\quad (ii) The {\bf complement} $\overline{G}$ of $G$ is the graph $(V,\overline{E})$ where $\overline{E}$ consists of just those edges between elements of $V$ which are not in $E$.
\quad (iii) A {\bf path} in $G$ is a string $\Matrix{v_0&v_1&\ldots&v_n}$ of vertices such that $v_i$, $v_{i+1}$ are linked by an edge for every $i0$ there is a $v_1\in V$ such that $v_0$ is linked to $v_0$ by an edge. For $n\ge 1$, given that we have chosen $v_{n-1}$ and $v_n$, let $v_{n+1}\in V$ be a vertex, other than $v_{n-1}$, linked to $v_n$ by an edge; such exists because $d(v_n)\ge 2$. In this way we obtain a sequence $v_0$, $v_1$, $v_2$, $v_3,\ldots$ such that $v_i$ is linked by an edge to $v_{i+1}$ for every $i$, but $v_i\ne v_{i+2}$ for every $i$.
Because $V$ is finite, the $v_i$ cannot all be distinct. Let $v_j$ be the first which is equal to some preceding one. Then
$v_0,\ldots,v_{j-1}$ are all distinct and $v_j=v_i$ for some $i1$, if $G$ has no cycle then there must be some $v\in V$ such that $d(v)\le 1$, by (b). Consider the graph $G'=G-v$ with vertex set $V'=V\setminus\{v\}$ and with all the edges
of $G$ except that one (if there is one) ending at $v$. Then surely $G'$ has no cycle, while its order $\#(V')$ is $n-1$, so by the inductive hypothesis $\#(E')<\#(V')$, where $E'$ is the set of edges of $G'$. But now
\Centerline{$\#(E)\le \#(E')+1<\#(V')+1=\#(V)$.}
\noindent So the induction proceeds.
}%end of ansBAa
\def\ansBAe{(e) Induce on $\#(E)$. If $\#(E)=0$ then $G$ can have at most one vertex, so $\#(V)\le 1=\#(E)+1$. For the inductive step to $\#(E)=m\ge 1$, consider two cases. (i) If $G$ has a cycle, $\Matrix{v_0&\ldots&v_n}$, delete the edge between $v_0$ and $v_1$ to form a graph $G'=(V,E')$ with $\#(E')<\#(E)$. But $G'$ is still connected. \Prf\ If $v\in V$, there is a simple path from $v$ to $v_0$ in $G$. If this is not itself a path in $G'$, that's because it contains the link $\Matrix{v_1&v_0}$. But now we can replace this link by the path $\Matrix{v_1&\ldots&v_n=v_0}$, which is a path in $G'$. Thus every vertex of $G'$ is joined to $v_0$ by a path in $G'$, and $G'$ is connected. \Qed\ By the inductive hypothesis,
\Centerline{$\#(V)\le\#(E')+1\le\#(E)+1$.}
\noindent (ii) If $G$ has no cycle, then by (b) there is a $v\in G$ such that $d(v)\le 1$. Of course $v$ is not the only vertex of $G$, because $G$ has an edge, so $d(v)=1$, because $v$ must be joined to another vertex by a path. As in (d), let $G'=(V',E')$ be the graph $G-v$, so that $\#(V')=\#(V)-1$ and $\#(E')=m-1$. Now again $G'$ is connected. \Prf\ If $u$, $w\in V'$ then they are joined by a simple path in $G$. But this simple path cannot pass through $v$, because $d(v)=1$, so any path using $v$ must use its unique neighbour twice. So it is a path in $G'$. \Qed\ By the inductive hupothesis,
\Centerline{$\#(V)=\#(V')+1\le\#(E')+2=\#(E)+1$.}
\noindent Thus in both cases the induction proceeds.
\medskip
(f)(i)$\Rightarrow$(ii)+(iii) If $G$ is a tree then $\#(E)<\#(V)$, by (d), and also $\#(E)\ge\#(V)-1$, by (e); so $\#(E)=\#(V)-1$ and both (ii) and (iii) are true.
\medskip
\quad (ii)$\Rightarrow$(i) Induce on $\#(E)$. If $\#(E)=0$ then of course $G$ has no cycle and is a tree. For the inductive step to
$\#(E)=m\ge 1$, \Quer\ suppose, if possible, that $G$ has a cycle $\Matrix{v_0&\ldots&v_n}$. As in (e) above, consider the graph $G'=(V,E')$ obtained by deleting this edge. This is still connected, and $\#(V)\ge\#(E')+1$. But $\#(E')1$, we know from (b) that $G$ has a vertex $v$ of degree at most 1. Consider the graph $G'=G-v=(V',E')$, as in (d) and (e). Of course $G'$ has no cycle, while
\Centerline{$\#(V')=\#(V)-1\le\#(E)\le\#(E')+1$;}
\noindent so by the inductive hypothesis, $G'$ is a tree and $\#(V')=\#(E')+1$. But this means that $\#(E)$ must be exactly $\#(E')+1$, so $d(v)=1$ in $G$. Now if $u$, $w\in V\setminus \{v\}=V'$, $u$ and $w$ are joined by a path in $G'$, and therefore in $G$; while $v$ is linked to some member of $V'$ by the edge starting at $v$, so is joined to every member of $V$ in $G$. Thus $G$ also is connected, and the induction proceeds.
}%end of ansBA
\def\qnBB{Describe the 34 isomorphism types of graphs on a given set of
5 vertices, and say how many graphs there are of each type. Check that
you have $^{10}C_k$ graphs with $k$ edges for each $k$.
\hfill[BB]}
\def\ansBBa{{\bf case 1} No edges, 5 components; 1 graph.
\Centerline{(No diagram available.)}%\picture{251-BB01}{50pt}
{\bf case 2} 1 edge, 4 components; $^5C_2=10$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB02}{50pt}
{\bf case 3} 2 edges, 3 components.
\quad{\bf case 3a} The edges share a vertex: $5.^4C_2=30$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB03}{50pt}
\quad{\bf case 3b} The edges don't share a vertex: $5.^4C_2/2=15$
graphs.
\Centerline{(No diagram available.)}%\picture{251-BB04}{50pt}
(That makes $45=^{10}C_2$ graphs with two edges.)
{\bf case 4} 3 edges, 3 components; the edges must be in a triangle;
$^5C_2=10$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB05}{50pt}
{\bf case 5} 3 edges, 2 components.
\quad{\bf case 5a} One of the components is a singleton. In this case
the remaining four vertices form a connected graph with three edges,
which must be a tree.
\qquad{\bf case 5a(i)} The tree is a simple path. $5!/2=60$ graphs.
(We can take the path in either direction.)
\Centerline{(No diagram available.)}%\picture{251-BB06}{50pt}
\qquad{\bf case 5a(ii)} The tree has a central division. $5.4=20$
graphs.
\Centerline{(No diagram available.)}%\picture{251-BB07}{50pt}
\quad{\bf case 5b} One of the components is a doubleton, the other a
triplet. $5$ choices of the central vertex of the triple, $^4C_2$
choices of its companions, making $5.6=30$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB08}{50pt}
(That makes $120=^{10}C_3$ graphs with 3 edges.)
{\bf case 6} 4 edges, 2 components.
\quad{\bf case 6a} One of the components is a singleton. In this case
the other has 4 edges and 4 vertices.
\qquad{\bf case 6a(i)} The 4-vertex component is a square. $5.3=15$
graphs. (Having picked the singleton, take any other vertex; there
are three choices of the {\it opposite} vertex of the square.)
\Centerline{(No diagram available.)}%\picture{251-BB09}{50pt}
\qquad{\bf case 6a(ii)} The 4-vertex component is a triangle with a tag
on. $5.4.3=60$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB10}{50pt}
\quad{\bf case 6b} One component has 2 vertices and the other has 3.
In this case they form a dumbbell and a triangle. $^5C_2=10$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB11}{50pt}
}%end of ansBBa
\def\ansBBb{{\bf case 7} 4 edges, 1 component. This must be a tree.
\quad{\bf case 7a} A simple path. $5!/2=60$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB12}{50pt}
\quad{\bf case 7b} A vertex of degree 3. $5.4.3=60$ graphs. (5
choices for the vertex of degree 3, 4 for its neighbour on the long arm,
3 for the end of the long arm.)
\Centerline{(No diagram available.)}%\picture{251-BB13}{50pt}
\quad{\bf case 7c} A vertex of degree 4. 5 graphs.
\Centerline{(No diagram available.)}%\picture{251-BB14}{50pt}
(That makes $210=^{10}C_4$ graphs with 4 edges.)
{\bf case 8} 5 edges, 2 components. One component must be a singleton
and the other is $K_4$ with one edge missing. $5.6=30$
graphs.
\Centerline{(No diagram available.)}%\picture{251-BB15}{50pt}
{\bf case 9} 5 edges, 1 component. This must have a cycle in it.
\quad{\bf case 9a} A simple cycle of length 5. $5!/10=12$ graphs.
(Take all lists of the 5 vertices; divide by 5 because we can start
anywhere along the cycle; divide by 2 because we can go in either
direction.)
\Centerline{(No diagram available.)}%\picture{251-BB16}{50pt}
\quad{\bf case 9b} A cycle of length 4 with one vertex off the side.
$5.4.3=60$ graphs. (5 choices for the vertex at the side, 4 for its
neighbour, 3 for the vertex opposite the neighbour.)
\Centerline{(No diagram available.)}%\picture{251-BB17}{50pt}
\quad{\bf case 9c} A 3-cycle:
\qquad{\bf case 9c(i)} The two other vertices attached to different
points of the cycle. $^5C_2$ choices of the odd vertices, $3!$ choices
of the others, $10.6=60$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB18}{50pt}
\qquad{\bf case 9c(ii)} The two other vertices attached in line.
$5.4.3=60$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB19}{50pt}
\qquad{\bf case 9c(iii)} The two other vertices attached at the same
point of the triangle. $5.^4C_2=30$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB20}{50pt}
(This makes $252=^{10}C_5$ graphs with 5 edges.)
{\bf The rest} are all complements of graphs with 4 or fewer edges, and
may therefore be counted out from the list above. Spelling them out,
we have
{\bf case 1'} 10 edges, $K_5$; 1 graph.
\Centerline{(No diagram available.)}%\picture{251-BB21}{50pt}
{\bf case 2'} 9 edges; $10$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB22}{50pt}
{\bf case 3'} 8 edges.
\quad{\bf case 3a'} The missing edges share a vertex: $30$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB23}{50pt}
\quad{\bf case 3b'} The missing edges don't share a vertex: $15$
graphs.
\Centerline{(No diagram available.)}%\picture{251-BB24}{50pt}
}%end of ansBBc
\def\ansBBc{{\bf case 4'} 7 edges, the missing edges in a triangle; that is, we
have two vertices joined to an edge and the other three joined just to
thos two; $10$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB25}{50pt}
{\bf case 5a(i)'} 7 edges, the three missing ones forming a simple path;
that is, we have a 5-cycle with two extra edges meeting at a vertex of
the cycle. 60 graphs.
\Centerline{(No diagram available.)}%\picture{251-BB26}{50pt}
{\bf case 5a(ii)'} 7 edges, the three missing ones meeting at a vertex;
that is, we have a $K_4$ with one extra vertex attached.
$20$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB27}{50pt}
{\bf case 5b'} 7 edges, two of the three missing edges meeting at a
vertex, the other disjoint from both; that is, we have a 5-cycle with
two extra edges not meeting at a vertex. $30$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB28}{50pt}
{\bf case 6a(i)'} 6 edges, two triangles meeting at a point. $15$
graphs.
\Centerline{(No diagram available.)}%\picture{251-BB29}{50pt}
{\bf case 6a(ii)'} 6 edges, a square with a diagonal and a tag attached
to one of the ends of the diagonal.
$60$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB30}{50pt}
{\bf case 6b'} 6 edges, $K_{2,3}$.
$10$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB31}{50pt}
{\bf case 7a'} 6 edges, a 5-cycle with one extra edge.
$60$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB32}{50pt}
{\bf case 7b'} 6 edges, a square with a diagonal and a tag attached to
one of the other vertices. $60$ graphs.
\Centerline{(No diagram available.)}%\picture{251-BB33}{50pt}
{\bf case 7c'} 6 edges, $K_4$ and a singleton. 5 graphs.
\Centerline{(No diagram available.)}%\picture{251-BB34}{50pt}
}
\def\qnBC{Describe the 5 isomorphism types of trees on a given set of 6
vertices, and say how many trees there are of each type.
\hfill[BC]}
\def\ansBC{{\bf case 1} A simple path. $6!/2=360$ trees.
{\bf case 2} A $Y$ with a long stem. $6!/2=360$ trees.
{\bf case 3} A $Y$ with a short stem. $6!/2=360$ trees.
{\bf case 4} A cross with one long arm. $6!/3=240$ trees.
{\bf case 5} An $H$. $6!/4=180$ trees.
(Total 1860 trees.)}
\def\qnBD{(a) Let $G$ be a finite graph with at least two vertices.
Show that $G$ has two vertices with the same degree.
(b) Explain how to construct an infinite graph with vertex set $\Bbb N$ in which the
vertex $n$ has degree $n$, for every $n$.
\hfill[BD]}
\def\ansBD{(No answer written out.)}
\def\qnBE{Let $G$ be a graph of order $n$ and with no triangles. Show
that (i) if $n=2k$ is even, then $G$ has at most $k^2=n^2/4=\lfloor
n^2/4\rfloor$ edges (ii) if $n=2k+1$ is odd, then $G$ has at most
$k(k+1)=(n^2-1)/4=\lfloor n^2/4\rfloor$ edges. ({\it Hint:} show
that $G$ has a vertex of degree not more than $\bover{n}2$, and induce on $n$.)
\hfill[BE]}
\def\ansBE{(No answer written out.)}
\def\qnBF{Let $G$ be a graph with vertex set $V$ and at least one edge. For $W\subseteq V$
let $G_W$ be the restriction of $G$ to $W$ and $e(G_W)$ the number of
edges of $G_W$. Show that there is a $W\subseteq G$ such that
$e(G_W)+e(G_{V\setminus W})<\bover12e(G)$ and
$\#(W)=\lfloor\bover12\#(V)\rfloor$. ({\it Hint:} suppose that $W$
is a random set of this size. Find the probability that any given edge
of $G$ is an edge of either $G_W$ or $G_{V\setminus W}$, and hence
calculate the expectation of $e(G_W)+e(G_{V\setminus W})$.)
\hfill[BF]}
\def\ansBF{Write $n=\#(V)$, $k=\lfloor\bover12n\rfloor$, so that $n$ is either $2k$ or $2k+1$; because $G$ has an edge, $n\ge 2$ and $k\ge 1$. Given that $e$ is an edge of $G$, the probability that $e$ is an edge of $G_W$ is the probability that both ends of $e$ are in $W$, that is,
\Centerline{$^{n-2}C_{k-2}/\ ^nC_k=\Bover{(n-2)!}{(k-2)!(n-k)!}
\Bover{k!(n-k)!}{n!}=\Bover{k(k-1)}{n(n-1)}$.}
\noindent Similarly, the probability that $e$ is an edge of $G_{V\setminus W}$ is
\Centerline{$^{n-2}C_{k}/\ ^nC_k=\Bover{(n-2)!}{k!(n-k-2)!}
\Bover{k!(n-k)!}{n!}=\Bover{(n-k)(n-k-1)}{n(n-1)}$.}
\noindent So the probability that $e$ is an edge of one or the other is
$$\eqalign{\Bover1{n(n-1)}(k(k-1)+(n-k)(n-k-1))
&=\Bover{2k(k-1)}{2k(2k-1)}=\Bover{k-1}{2k-1}\text{ if }n=2k,\cr
&=\Bover{2k^2}{2k(2k+1)}=\Bover{k}{2k+1}\text{ if }n=2k+1.\cr}$$
Now this means that the expectation of $e(G_W)+e(G_{V\setminus W})$ is either $\bover{k-1}{2k-1}e(G)$ or $\bover{k}{2k+1}e(G)$, and in either case is less than $\bover12 e(G)$. There must therefore be at least one $W$ such that $e(G_W)+e(G_{V\setminus W})<\bover12e(G)$.
(This argument assumes implicitly that $k\ge 2$. But if $k=1$ then $n$ is either $2$ or $3$. If $n=2$ we take $W$ a singleton and get $e(G_W)+e(G_{V\setminus W})=0<\bover12e(G)$. If $n=3$, then if $G$ has $1$ or $2$ edges we can again pick $W$ so that $e(G_W)+e(G_{V\setminus W})=0<\bover12e(G)$, while if $G$ has $3$ edges we can pick $W$ sush that $e(G_W)+e(G_{V\setminus W})=1<\bover12e(G)$.)
}%end of ansBF
\def\qnBG{Let $G$ be a graph with vertices $v_1,\ldots,v_n$, and suppose
that $d(v_1)\le d(v_2)\le\ldots\le d(v_n)$, where $d(v)$ is the degree
of the vertex $v$. Suppose that $d(v_k)\ge k$ for $1\le k1$, if $i\#(I)$ for every non-empty $I\subseteq X$,
show that any $x\in X$ has this property. Otherwise take $x$ to belong
to some minimal $I$ such that $\#(R[I])=\#(I)$.)
\hfill[EG]}
\def\ansEG{(No answer written out.)}
\def\qnEH{Let $\tbf{A}$ be a {\it doubly stochastic} square matrix, that
is, an $n\times n$ matrix such that $a_{ij}\ge 0$ for all $i$, $j$ and
$\sum_{i=1}^na_{ik}=\sum_{j=1}^na_{kj}=1$ for every $k\le n$. Show
that there is a permutation $\rho$ of $\{1,\ldots,n\}$ such that
$a_{i,\rho(i)}>0$ for evey $i\le n$.
\hfill[EH]}
\def\ansEH{(No answer written out.)}
\def\qnEI{(a) Define {\it partially ordered set}, {\it totally ordered
set}.
(b) State and prove {\it Dilworth's theorem}.
\hfill[EI]}
\def\ansEI{(No answer written out.)}
\def\qnEJ{Let $V$ be a set with $n\ge 1$ members, and set $r=\lfloor
\bover{n}2\rfloor$. Show that the partially ordered set $\Cal PV$
can be expressed as a union of ${^nC_r}$ totally ordered subsets, but not
fewer. ({\it Hint:} recall that for $k<\bover{n}2$ there is an
injective function $f:[V]^k\to [V]^{k+1}$ such that $a\subseteq f(a)$
for $a\in [V]^k$. Show that for $\bover{n}2\le k