Lesson 1

Basic Problems.

1. (10 points) Let \(G\) be a flow network with source \(s\), sink \(t\), and a positive integer capacity \(c_{e}\) on every edge \(e\). Let \((A,B)\) be a minimum \(s\)-\(t\) cut with respect to the capacities \(\{c_{e}\}\). Now increase every capacity by \(1\), i.e., replace each \(c_{e}\) with \(c_{e}+1\). Must \((A,B)\) still be a minimum \(s\)-\(t\) cut for the new capacities?
   Hint:

   Compare how the value of a fixed cut changes when every crossing edge gains the same extra \(1\).
2. (10 points) Let \((S_{1},T_{1})\) and \((S_{2},T_{2})\) be minimum \(s\)–\(t\) cuts in a network \(G\). Prove that the cuts \((S_{1} \cap S_{2}, T_{1} \cup T_{2})\) and \((S_{1} \cup S_{2}, T_{1} \cap T_{2})\) are also minimum.
3. (10 points) A flow in a network is called acyclic if the subgraph consisting of all edges with non-zero flow is acyclic. Prove that for any flow there exists an acyclic flow with the same value as the original one.
   Hint:

   If the support contains a directed cycle, try modifying the flow only along this cycle.
4. (10 points) Given a graph \(G=(V,E)\) and an integer \(k\ge 0\), define a relation \(\sim\) on vertices by declaring \(x\sim y\) if there exist \(k\) mutually edge-disjoint paths from \(x\) to \(y\) in \(G\). Is \(\sim\) transitive for every \(G\) and every \(k\)? (That is, does \(x\sim y\) and \(y\sim z\) always imply \(x\sim z\)?) Give a proof or a counterexample.
5. (15 points) Let \(Q_{d}\) be the \(d\)-dimensional hypercube graph with vertex set \(\{0, 1\}^{d}\), where edges connect vertices with Hamming distance \(\operatorname{dist}(u, v) = 1\). Let \(s = 0^{d}\) and \(t = 1^{d}\). Give an explicit construction of a maximum family of internally vertex-disjoint paths from \(s\) to \(t\).
6. (15 points) Let graph \(G\) be vertex \(k\)-connected. Form a new graph \(G'\) from \(G\) by adding to \(G\) a new vertex \(y\) and at least \(k\) edges from \(y\) to \(k\) different vertices of the graph \(G\). Prove that the graph \(G'\) is also vertex \(k\)-connected.
   Hint:

   Assume a separating set of size \(<k\) exists in \(G'\) and consider whether it contains \(y\).
7. (15 points) Prove that a simple graph \(G\) with three or more vertices is biconnected if and only if for any triple of distinct vertices \((x,y,z)\) in \(G\) there is a simple path from \(x\) to \(z\) passing through \(y\).
   Hint:

   Relate the condition to the existence (or absence) of articulation vertices.
8. (15 points) There are \(3k\) departments in a university. To form the Academic Council, one needs to select exactly one lecturer from each of the university departments. One lecturer can be assigned to one or more departments but can be elected to the Academic Council only from one of them. There are professors, associate professors and assistant professors in the university (so each faculty member has the same rank in all departments). The same number of faculty members from each of these three ranks must be on the Academic Council. Construct a network to select faculty members for the Academic Council.
9. (15 points) Let \(A\) be an \(n\times m\) matrix of non-negative real numbers such that the sum of the entries is an integer in every row and in every column. Prove that there is an \(n\times m\) matrix \(B\) of non-negative integers with the same sums as in \(A\), in every row and every column.
   Hint:

   Encode row sums and column sums as capacities in a bipartite flow network, then use integrality of max flow.
10. (15 points) Deduce Hall's theorem from the max-flow min-cut theorem. Hall's theorem states that in a bipartite graph \(G(X \sqcup Y, E)\) a matching saturating \(X\) exists if and only if for any subset \(S \subseteq X\), it holds that \(|S| \le |N(S)|\).
    Hint:

    Build a unit-capacity flow network from a bipartite graph and interpret the capacity of certain cuts using neighborhoods.
11. (15 points) For every integer \(n\ge 1\), construct an explicit family \(\{G_{n}\}\) of flow graphs with \(O(n)\) vertices and edges and with distinguished vertices \(s,t\), such that the number of distinct minimum \(s\)–\(t\) cuts in \(G_{n}\) is at least \(2^{n}\).
12. (15 points) A strong orientation of an undirected graph is a choice of direction for each of its edges such that the resulting directed graph is strongly connected. Prove that a connected graph admits a strong orientation if and only if it is \(2\)-edge-connected (that is, there are no bridges in it).
    Hint:

    If there is a bridge, any orientation of it blocks travel in one direction. For the converse, try building the orientation starting from a cycle.
13. (15 points) Let \(G\) be a biconnected graph on \(n\) vertices, and let \(n_{1},n_{2}\in\mathbb{N}\) satisfy \(n_{1}+n_{2}=n\). Let \(M\subseteq V(G)\) be a connected set such that the induced subgraph \(G[V(G)\setminus M]\) is connected, let \(v_{2}\in V(G)\setminus M\), and assume \(|M|\le n_{1}\). Prove that the vertex set can be split into two subsets \(V_{1}\supseteq M\) and \(V_{2}\ni v_{2}\) such that \(|V_{1}|=n_{1}\), \(|V_{2}|=n_{2}\), and the induced subgraphs \(G[V_{1}]\) and \(G[V_{2}]\) are connected.
    Hint:

    Start with the partition \((M,\ V(G)\setminus M)\) and move vertices one at a time while keeping both induced subgraphs connected.