\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Selected Solutions -- Problem Set 7}
\centerline{April 11, 2005}
\bigskip
\noindent
Chapter 9/3.  Let $G = (X,\Delta,Y)$ be any bipartite graph.
Write $X = \{x_1,\ldots,x_m\}$ and $Y = \{y_1,\ldots,y_n\}$.
The board $B = B(G)$ constructed as follows has 
$G$ as its rook-bipartite graph:  $B(G)$ is $m\times n$
and the square in row $i$ and column $j$ is unshaded if and 
only if $\{x_i,y_j\}$ is in $\Delta$ (represents an edge in $G$).  
\bigskip
\noindent
Chapter 9/7.  Let $G = (X,\Delta,Y)$ be the bipartite graph.
Every edge connects a vertex in $X$ to a vertex in $Y$ by the 
definition of a bipartite graph.  
Since each vertex in $X$ meets at least $p$ edges, 
$|\Delta| \ge p|X|$.  Similarly, since each vertex in $Y$ meets
at most $p$ edges, $|\Delta| \le p|Y|$.  Combining these
inequalities and then dividing by the positive number $p$,
$$p|X| \le |\Delta| \le p|Y| \Rightarrow |X| \le |Y|,$$
which is what we wanted to show.
\bigskip
\noindent
Chapter 9/13.  The general statement is:  Let 
$${\cal A} = (A_1,A_2,\ldots,A_{n-1},A_n) = (\{1,2\},\{2,3\},\ldots,\{n-1,n\},\{n,1\}).$$
Then ${\cal A}$ has exactly two SDR's:
$$\cases{1\in A_1 & \cr
2\in A_2 & \cr
3\in A_3 & \cr
\vdots & \cr
n\in A_n & \cr} \qquad {\rm and} \qquad 
\cases{2\in A_1 & \cr
3\in A_2 & \cr
4\in A_3 & \cr
\vdots & \cr
1\in A_n & \cr}$$
\bigskip
\noindent
{\bf Proof:}  It is clear that these are SDR's for ${\cal A}$.  To 
show that they are the {\it only} ones,  note that the only two possible
representatives for $A_1 = \{1,2\}$ are $1$ and $2$.  So it is enough
to show that if $1$ represents $A_1 = \{1,2\}$, then the other representatives
are ``forced'' to be as in the first SDR above, and that if 
$2$ represents $A_1$, then the other representatives are forced to 
be as in the second.  But if $1$ represents $A_1$, then $1$ cannot
represent $A_n = \{n,1\}$, so $n$ must represent $A_n$, and then 
$n - 1$ must represent $A_{n-1} = \{n-1,n\}$, 
$n - 2$ must represent $A_{n-2} = \{n-2,n-1\}$, and so on until we see
$2$ must represent $A_2 = \{2,3\}$.  This gives the first SDR above.
Similarly, if $2$ represents $A_1$, then $2$ cannot represent $A_2 = \{2,3\}$, so 
the only choice is for $3$ to represent $A_2$, $4$ to represent $A_3$, 
and so on until $1$ represents $A_n$.  This gives the second SDR above.
\bigskip
\noindent
Chapter 9/14.  Suppose that ${\cal A}=(A_1,\ldots,A_n)$ has some SDR,
but no SDR contains $x\in A_1$.  Then we have some SDR
$$\cases{a_1\in A_1 & \cr
a_2\in A_2 & \cr
a_3\in A_3 & \cr
\vdots & \cr
a_n\in A_n & \cr}$$
where the $a_i$ are distinct and all different from $x$.  But
then $a_1 \ne x \in A_1$, so we could create another SDR by 
simply replacing $a_1$ by $x$:
$$\cases{x\in A_1 & \cr
a_2\in A_2 & \cr
a_3\in A_3 & \cr
\vdots & \cr
a_n\in A_n & \cr}$$
This leads to a contradiction.  So some SDR for ${\cal A}$ must
contain $x$.  
\bigskip
It is not always the case, though, that 
$x$ represents $A_1$.  For instance, let ${\cal A}=(\{x,y\},\{x\})$.
Then $x$ must represent $A_2$ and $y$ must represent $A_1$ in the 
only SDR that is present.
\bigskip
\noindent
Chapter 9/15.  Assume ${\cal A} = (A_1,\ldots,A_n)$
satisfies
$$\left|\bigcup_{i\in I} A_i\right| \ge |I| + 1\leqno(1)$$
for all $I \subseteq \{1,\ldots,n\}$.  To make an SDR of ${\cal A}$
where $x$ represents $A_1$, we only need to show that we can find
$a_2 \in A_2, \ldots, a_n \in A_n$ that are distinct and all different
from $x$.  This is the same as an SDR of the family 
$${\cal A}' = (A_2 - \{x\},\ldots, A_n - \{x\}).$$
By Hall's Theorem, it is enough to show that the ``Marriage Condition''
is satisfied by ${\cal A}'$.  But for any $J \subseteq \{2,\ldots,n\}$,
by (1) we have 
$$\left|\bigcup_{j\in J} (A_j - \{x\})\right| \ge |I| + 1 - 1 = |I|,$$
since in forming the union $\cup_{j\in J} (A_j - \{x\})$ we 
omit at most the one element $x$ from $\cup_{j\in J} A_j$.  Hence
the ``Marriage Condition'' is satisfied for ${\cal A}'$ and 
we can find $a_2, \ldots, a_n$ as above to make an SDR of ${\cal A}$
in which $x$ represents $A_1$.
\bigskip
\noindent
Chapter 11/5.  Given a graph $G$ of order $n \ge 2$, we are always
in one of the following two cases.
\bigskip
\noindent
Case I:  There is some vertex $x$ of $G = (V,E)$ of degree $n-1$ (so there is
an edge from $x$ to every $y \ne x$ in $V$).  In this case, all degrees
of vertices are at least $1$ so the 
set of possible degrees of vertices is $\{1,2,\ldots,n-1\}$.  By 
the pigeonhole principle, since there are $n$ vertices, two of them
must have the same degree.
\bigskip
\noindent
Case II:  There is no vertex of degree $n-1$. Then the set of possible
degrees is $\{0,1,2,\ldots,n-2\}$. 
(Note:  Case II {\it does not}
imply that there has to be a vertex of degree 0, only that it is now
possible for some vertex to have degree 0(!).  It is 
possible for a graph to have no vertex of degree $n-1$ {\it and} no vertex
of degree 0.  Find an example to convince yourself!)
 By the pigeonhole principle again,
two vertices must have the same degree, because there are only $n-1$
possible degrees, but $n$ vertices.
\bigskip
\noindent
This statement is not true for multigraphs.  For instance, the multigraph
\bigskip
\noindent
has three vertices of degrees $1,2,3$ respectively.  
\bigskip
\noindent
Chapter 11/10.  One example of a connected graph of order $n$ with degree
sequence $(2,2,\ldots,2)$ is $G = (V,E)$ with 
$$\eqalign{V &=\{x_1,\ldots,x_n\}\cr
           E &= \{\{x_1,x_2\},\ldots,\{x_{n-1},x_n\},\{x_n,x_1\}\}:\cr}$$
\bigskip
\bigskip
\noindent
We will show first that any other $G' = (V',E')$ satisfying these 
hypotheses is isomorphic to $G$.  So let $V' = \{y_1,\ldots,y_n\}$.
We will define the isomorphism $\phi:V \to V'$ step by step.  First let 
$\phi(x_1) = y_1$ (any other choice would work too!).  $x_1$ is 
connected by an edge to $x_2$ in $G$, so let $y_{k_2}$ be either one of the
two vertices in $G'$ connected by an edge to $y_1$, and define 
$\phi(x_2) = y_{k_2}$.
Now, since $G'$ has degree sequence $(2,2,\ldots,2)$, in $G'$, $y_{k_2}$
is connected by an edge to exactly one vertex different from $y_1$, say $y_{k_3}$.  Let
$\phi(x_3) = y_{k_3}$.  Then $y_{k_2}$
is connected by an edge to exactly one vertex other than $y_{k_3}$, say
$y_{k_4}$.  Define $\phi(x_4) = y_{k_4}$.  Continue in the same way
to define $\phi(x_\ell) = y_{k_\ell}$ for all $\ell = 2, \ldots, n$, 
where at each step, $y_{k_\ell}$ is the vertex in $G'$ connected by an edge to 
$y_{k_{\ell-1}}$ that is different from $y_{k_{\ell-2}}$.
By construction, $y_1,y_{k_2},\ldots,y_{k_n}$ are distinct, so 
they account for all of the vertices of $G'$.  Also, by construction,
there is one additional edge in $G'$ from $y_{k_n}$ to some other
vertex.  The only possibility is for that edge to connect $y_{k_n}$
back to $y_1$, since we have already ``used'' two edges at each of 
the $y_{k_\ell}$ for $\ell = 2,\ldots, n$.  Therefore $\phi$ is an 
isomorphism from $G$ to $G'$ because there is an edge from 
$x_i$ to $x_j$ in $G$ if and only if there is an edge from 
$\phi(x_i)$ to $\phi(x_j)$ in $G'$.  

Now, to ``nail down'' the proof of the result of the problem we
note that isomorphism of graphs is an {\it equivalence relation}
(it is a reflexive, symmetric, and transitive relation).  Hence
the argument above shows that if we have any two graphs $G'$ and $G''$
satisfying our hypotheses, then $G'$ is isomorphic to the standard
$G$ as above, and so is $G''$.  But then by symmetry and transitivity,
$G'$ and $G''$ are also isomorphic to each other.
\bye
