Assignment 8-

1. Let A be a finite set with subsets A₁, . . . , A_n and let d₁, d₂, . . . , d_n be positive integers. Show that there are disjoint subsets D_k ⊂ A_k with |Dk| = d_k for all k, if and only if |∪_i∈IA_i| ≥ Σ_i∈Id_i for every I ⊂ {1, 2, . . . , n}.

2. Let G be a 3-regular connected graph that has no bridge, with |V (G)| ≥ 3. Prove G has a perfect matching.

3. Find a maximum flow in the network below from the source S to the sink T. Justify that your flow is a maximum flow.

4. Let G be a graph and s, t ∈ V (G). A set K ⊂ E(G) is said to separate s from t if every path from s to t in G uses some edge in K. Using network flow theory, prove that the minimum number of edges needed to separate s from t is equal to the maximum number of edge-disjoint paths from s to t. (Hint: Create a directed multi-graph. Depending on how you do this, you may or may not want edges going both in and out of both the source and sink.)

5. For any positive integer n, let G_n be the graph whose vertex set is the set of n-element subsets of {1, 2, 3, . . . , 2n + 1}, with two vertices adjacent if and only if they have no elements in common. For instance, below is the graph G₂.

Determine all positive integers n for which G_n is planar.

6. Soccer balls typically consist of hexagonal faces and pentagonal faces, with all vertices where faces meet having degree exactly 3. By considering this as a planar graph, show that regardless of the number of hexagonal faces, there must always be exactly 12 pentagonal faces.