Mathematics 357 – Combinatorics Selected Solutions – Problem Set 7 April 11, 2005

Chapter 9/3. Let G = (X, Δ, Y) be any bipartite graph. Write X = {x_{1}, …, x_{m}} and Y = {y_{1}, …, y_{n}}. The board B = B(G) constructed as follows has G as its rook-bipartite graph: B(G) is m × n and the square in row i and column j is unshaded if and only if {x_{i}, y_{j}} is in Δ (represents an edge in G).

Chapter 9/7. Let G = (X, Δ, 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, |Δ| ≥ p|X|. Similarly, since each vertex in Y meets at most p edges, |Δ| ≤ p|Y |. Combining these inequalities and then dividing by the positive number p,

p|X| ≤ |Δ| ≤ p|Y | ⇒ |X| ≤ |Y |,

which is what we wanted to show.

Chapter 9/13. The general statement is: Let

A = (A_{1}, A_{2}, …, A_{n−1}, A_{n}) = ({1, 2}, {2, 3}, …, {n − 1, n}, {n, 1}).

Then A has exactly two SDR’s:

{ 1 ∈ A_{1} ; 2 ∈ A_{2} ; 3 ∈ A_{3} ; ⋮ ; n ∈ A_{n}  and  { 2 ∈ A_{1} ; 3 ∈ A_{2} ; 4 ∈ A_{3} ; ⋮ ; 1 ∈ A_{n}

Proof: It is clear that these are SDR’s for A. To show that they are the 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.

Chapter 9/14. Suppose that A = (A_{1}, …, A_{n}) has some SDR, but no SDR contains x ∈ A_{1}. Then we have some SDR

{ a_{1} ∈ A_{1} ; a_{2} ∈ A_{2} ; a_{3} ∈ A_{3} ; ⋮ ; a_{n} ∈ A_{n}

where the a_{i} are distinct and all different from x. But then a_{1} ≠ x ∈ A_{1}, so we could create another SDR by simply replacing a_{1} by x:

{ x ∈ A_{1} ; a_{2} ∈ A_{2} ; a_{3} ∈ A_{3} ; ⋮ ; a_{n} ∈ A_{n}

This leads to a contradiction. So some SDR for A must contain x.

It is not always the case, though, that x represents A_{1}. For instance, let A = ({x, y}, {x}). Then x must represent A_{2} and y must represent A_{1} in the only SDR that is present.

Chapter 9/15. Assume A = (A_{1}, …, A_{n}) satisfies

(1)  |⋃_{i∈I} A_{i}| ≥ |I| + 1

for all I ⊆ {1, …, n}. To make an SDR of A where x represents A_{1}, we only need to show that we can find a_{2} ∈ A_{2}, …, a_{n} ∈ A_{n} that are distinct and all different from x. This is the same as an SDR of the family

A′ = (A_{2} − {x}, …, A_{n} − {x}).

By Hall’s Theorem, it is enough to show that the “Marriage Condition” is satisfied by A′. But for any J ⊆ {2, …, n}, by (1) we have

| ⋃_{j∈J}(A_{j} − {x})| ≥ |I| + 1 − 1 = |I|,

since in forming the union ∪_{j∈J}(A_{j} −{x}) we omit at most the one element x from ∪_{j∈J}A_{j}. Hence the “Marriage Condition” is satisfied for A′ and we can find a_{2}, …, a_{n} as above to make an SDR of A in which x represents A_{1}.

Chapter 11/5. Given a graph G of order n ≥ 2, we are always in one of the following two cases.

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 ≠ 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, …, n − 1}. By the pigeonhole principle, since there are n vertices, two of them must have the same degree.

Case II: There is no vertex of degree n−1. Then the set of possible degrees is {0, 1, 2, …, n− 2}. (Note: Case II 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 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.

This statement is not true for multigraphs. For instance, the multigraph

has three vertices of degrees 1, 2, 3 respectively.

Chapter 11/10. One example of a connected graph of order n with degree sequence (2, 2, …, 2) is G = (V, E) with

\begin{aligned}V & = \{x_{1}, …, x_{n}\} \\ E & = \{\{x_{1}, x_{2}\}, …, \{x_{n−1}, x_{n}\}, \{x_{n}, x_{1}\}\} : \end{aligned}

We will show first that any other G′ = (V′, E′) satisfying these hypotheses is isomorphic to G. So let V′ = {y_{1}, …, y_{n}}. We will define the isomorphism ϕ : V → V′ step by step. First let ϕ(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 ϕ(x_{2}) = y_{k_{2}}. Now, since G′ has degree sequence (2, 2, …, 2), in G′, y_{k_{2}} is connected by an edge to exactly one vertex different from y_{1}, say y_{k_{3}}. Let ϕ(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 ϕ(x_{4}) = y_{k_{4}}. Continue in the same way to define ϕ(x_{ℓ}) = y_{k_{ℓ}} for all ℓ = 2, …, n, where at each step, y_{k_{ℓ}} is the vertex in G′ connected by an edge to y_{k_{ℓ−1}} that is different from y_{k_{ℓ−2}}. By construction, y_{1}, y_{k_{2}}, …, 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_{ℓ}} for ℓ = 2, …, n. Therefore ϕ 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 ϕ(x_{i}) to ϕ(x_{j}) in G′.

Now, to “nail down” the proof of the result of the problem we note that isomorphism of graphs is an 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.