Let \(G\) be a graph and let \(M_0\) be any matching in \(G\text{.}\) Prove that \(G\) has a matching \(M\) of maximum cardinality which saturates every vertex vertex that is saturated by \(M_0\text{.}\)
Prove or disprove the following statement: Every tree has at most one perfect matching.
Prove or disprove the following statement: If \(G\) is a graph of minimum degree at least two which contains a perfect matching \(M\text{,}\) then it contains another perfect matching \(M'\neq M\text{.}\)
Prove or disprove the following statement: If \(G\) is a bipartite graph of minimum degree at least two which contains a perfect matching \(M\text{,}\) then it contains another perfect matching \(M'\neq M\text{.}\)
Let \(G\) be a bipartite graph with bipartition \((X,Y)\text{.}\) Prove that if \(C_1\) and \(C_2\) are a vertex covers in \(G\text{,}\) then so is
\begin{equation*}
(X\cap C_1\cap C_2)\cup (Y\cap(C_1\cup C_2)).
\end{equation*}
Let \(G\) be a bipartite graph with bipartition \((X,Y)\) with \(|X|=|Y|=n\text{.}\) Prove that if \(|E(G)|>(k-1)n\text{,}\) then \(G\) contains a matching with \(k\) edges.
Prove that every graph \(G\) with \(n\) vertices contains a matching of cardinality \(\min\{n,2\delta(G)\}\) where \(\delta(G)\) is the minimum degree of a vertex of \(G\text{.}\)
Define a line in a matrix to be a row or a column. Prove that, in any matrix \(M\text{,}\) the maximum number of non-zero entries in \(M\) such that no two of them lie in the same line is equal to the minimum number of lines that include all of the non-zero entries.
Use Kőnig’s Theorem to prove Hall’s Theorem.
Use (one of the versions of) Menger’s Theorem to prove Kőnig’s Theorem.
Use Kőnig’s Theorem to prove Dilworth’s Theorem (
Theorem 1.1.12).
Hint: Make two copies of the poset
\(P\text{.}\) Each copy will be one side of the bipartite graph.
Given a family \(\mathcal{A}\) of subsets of a set \(X\text{,}\) a system of distinct representatives (SDR) is a function \(f:\mathcal{A}\to X\) such that \(f(A)\in A\) for all \(A\in \mathcal{A}\) and, if \(A,B\in\mathcal{A}\) with \(A\neq B\text{,}\) then \(f(A)\neq f(B)\text{.}\) Prove that a finite collection \(\mathcal{A}\) of sets has a system of distinct representatives if and only if \(\left|\bigcup_{B\in\mathcal{B}}B\right|\geq |\mathcal{B}|\) holds for every \(\mathcal{B}\subseteq \mathcal{A}\text{.}\)
For \(k\geq1\text{,}\) let \(G\) be a \(k\)-regular bipartite graph with bipartition \((A,B)\) and let \(X\subseteq E(G)\) with \(|X|\leq k-1\text{.}\) Show that \(G\setminus X\) has a perfect matching.
For \(k\geq1\text{,}\) let \(G\) be a connected \(k\)-regular bipartite graph. Prove that any graph obtained by deleting two vertices of \(G\text{,}\) one from each side of the bipartition, has a perfect matching.
A Latin rectangle is a \(k\times n\) matrix such that each symbol in \(\{1,\dots,n\}\) appears exactly once in each row and at most once in each column. If \(k=n\text{,}\) then it is called a Latin square. Prove that, for all \(n\geq k\geq 1\text{,}\) every \(k\times n\) Latin rectangle is contained in an \(n\times n\) Latin square.
Let \(X\) be a set of cardinality \(nm\) and let \(\mathcal{A}=\{A_1,\dots,A_n\}\) and \(\mathcal{B}=\{B_1,\dots, B_n\}\) be two partitions of \(X\) into sets of cardinality exactly \(m\text{.}\) Prove that there exists a permutation \(\pi:\{1,\dots,n\}\to\{1,\dots,n\}\) such that all of the sets \(A_i\cap B_i\) for \(1\leq i\leq n\) are non-empty. Using this, prove that \(X\) can be partitioned into \(m\) sets, each of which is an SDR for both \(\mathcal{A}\) and \(\mathcal{B}\text{.}\)
A square matrix \(A\) is doubly stochastic if every entry is non-negative and the entries within any row or column sum to one. A permutation matrix is a square matrix in which every entry is in \(\{0,1\}\) and each row or column contains exactly one 1. Prove that every doubly stochastic matrix can be written as a convex combination of permutation matrices. Hint 1: The support of the matrix is the set of non-zero entries. Proceed by induction on the size of the support. Can you find a permutation matrix using entries from the support? If you can, how can you use it? Hint 2: Use Hall’s Theorem.
Prove
Lemma 3.2.4.
Hint: There is more than one way to do this. One way involves making two copies of the graph and adding edges between them in a clever way.
Let \(G\) be a bipartite graph and let \(c:E(G)\to \mathbb{N}\cup \{0\}\) be a weight function for the edges of \(G\text{.}\) Prove that the maximum weight of a matching in \(G\) is equal to the minimum value of \(\sum_{v\in V(G)}f(v)\) where \(f:V(G)\to\mathbb{N}\cup \{0\}\) is a function such that \(f(u)+f(v)\geq c(uv)\) for every edge \(uv\in E(G)\text{.}\) Hint: Use Egerváry’s Theorem and find a way to shift values in the dual vector to be integer.
A stable set in a graph \(G\) is a set \(S\) of vertices such that no two vertices in \(S\) are adjacent. The maximum cardinality of a stable set in \(G\) is denoted \(\alpha(G)\text{.}\) Let \(A\) and \(B\) be disjoint stable sets in a graph \(G\) such that \(|A|=\alpha(G)\text{.}\) Prove that there is a matching in \(G\) which saturates \(B\text{.}\)
A permutation of \(\{1,\dots,n\}\) is a sequence of length \(n\) containing every element of this set exactly once. For \(n\geq1\text{,}\) let \(\pi_1,\dots,\pi_k\) be permutations of \(\{1,\dots,n\}\text{.}\) Prove that, if \(k\leq n/2\text{,}\) then there exists a permutation \(\pi\) of \(\{1,\dots,n\}\) which differs from all of the permutations \(\pi_1,\dots,\pi_k\) in every position.
Let \(G\) be a graph and consider the following game with two players. The players alternate selecting vertices of the graph where, in the first round, Player 1 selects any vertex that they want and, after that, each vertex chosen must be a neighbour of the vertex chosen before it and must be different from all vertices chosen so far. The last player to select a vertex wins. Prove that Player 2 has a winning strategy if \(G\) has a perfect matching and that Player 1 has a winning strategy if \(G\) does not have a perfect matching.
Let \(G\) be a bipartite graph with bipartition \((A,B)\) and suppose that there is a matching in \(G\) which saturates \(A\text{.}\) Prove that the number of edges in \(G\) that are not contained in a matching of cardinality \(|A|\) is at most \(\binom{|A|}{2}\text{.}\)
Prove that if \(G\) is a bipartite graph with bipartition \((A,B)\) with \(|A|\leq |B|\text{,}\) then there exists a maximal path in \(G\) (i.e. a path that cannot be extended to a longer path by adding one vertex at one of the ends) with at least one endpoint in \(B\text{.}\)
Imagine that you are the boss of a company that produces vehicles and you are trying to assign \(n\) employees to \(n\) tasks such that each employee does exactly one task. Each employee has a certain skill level for each given task. If any employee is assigned to a task that they are not very skilled at, then it will hold back the production of vehicles. So, you want to assign employees to tasks in a way that maximizes the minimum skill level of each employee for the task that it is assigned to. We abstract this and reduce it to an LP as follows. Let \(G=(V,E)\) be a bipartite graph and let \(w:E\to [0,\infty)\) be a weight function. Write down a linear program for computing the maximum over all perfect matchings \(M\) of the minimum weight of an edge in \(M\text{.}\)
Let \(G\) be a bipartite graph and let \(w:V(G)\to \mathbb{R}\) be a weight function on the vertices. Describe an algorithm (without reducing the problem to linear programming) to find a minimum weight vertex cover in \(G\text{.}\)
-
Consider the following two problems.
Problem 3.8.1. Shortest Odd Path.
Let \(G\) be a graph, let \(s,t\in V(G)\) and let \(\ell:E(G)\to[0,\infty)\) be a length function. Find a path from \(s\) to \(t\) with an odd number of edges of minimum length.
Problem 3.8.2. Minimum Weight Perfect Matching.
Let \(G\) be a graph and \(w:E(G)\to\mathbb{R}\) be a weight function. Find a perfect matching in \(G\) of minimum weight.Prove that the Shortest Odd Path Problem can be reduced in polynomial time to the Minimum Weight Perfect Matching Problem. Hint: Make two copies of \(G\) with the weight of each edge being its length and, for each \(v\in V(G)\text{,}\) add an edge of weight zero between the two copies of \(v\text{.}\) Then, delete some vertices in a clever way and see what you get from a minimum weight perfect matching.
A graph is
\(k\)-regular if every vertex of it has degree equal to
\(k\text{;}\) i.e. there are exactly
\(k\) edges containing every vertex. Prove that if
\(G\) is a
\(k\)-regular
\((k-1)\)-edge connected graph (the definition is in
Section 3.6) with an even number of vertices and
\(w:E\to[0,\infty)\) is a weight function, then there exists a perfect matching
\(M\) in
\(G\) with
\(w(M)\geq \frac{1}{k}\sum_{e\in E}w(e)\text{.}\) Hint: Find an appropriate feasible point in the perfect matching polytope (and prove that it is feasible).
Theorem 3.5.3,
Theorem 3.6.9 and “Handshaking” may help.
Recall the definition of adjacent vertices of a polyhedron from
Exercise 12. For two matchings
\(M\) and
\(M'\) in a graph
\(G\text{,}\) explain what it means for the indicator vectors of
\(M\) and
\(M'\) to be adjacent vertices of the matching polytope of
\(G\text{.}\)
Let \(k\geq1\) be an integer. Come up with a characterization of graphs \(G\) with the property that the edges of \(G\) can be oriented so that the in-degree of each vertex is at most \(k\text{.}\) Your characterization should make it easy to argue the decision problem asking if such an orientation exists is in co-NP. Hint: Use Hall’s Theorem. You may need to do a few modifications to the graph first.
A tournament is a digraph obtained from a complete graph by orienting each edge toward one of its endpoints. Obtain a characterization of the sequences \((d_1,\dots,d_n)\) with the property that there exists a tournament \(T\) on vertex set \(v_1,\dots,v_n\) where the outdegree of \(v_i\) is equal to \(d_i\) for all \(1\leq i\leq n\text{.}\) Your characterization should make it easy to see that the decision problem if such a tournament exists is in co-NP. Hint: Use Hall’s Theorem.
Let \(G\) be a bipartite graph with bipartition \((A,B)\) where \(A=\{a_1,\dots,a_n\}\) and \(B=\{b_1,\dots,b_n\}\text{.}\) For each edge \(a_ib_j\) of \(G\text{,}\) let \(x_{i,j}\) be a real variable and let \(M\) be the \(n\times n\) matrix where the entry on the \(i\)th row and \(j\)th column is equal to \(x_{i,j}\) if \(a_ib_j\in E(G)\) and is equal to zero otherwise. Prove that \(G\) has a perfect matching if and only if there exists a choice of the variables such that \(\det(M)\neq 0\text{.}\)
Determine the number of perfect matchings in \(K_{n,n}\) and \(K_{2n}\) for all \(n\geq1\text{.}\)
Let \(G\) be a bipartite graph and let \(k\geq1\text{.}\) Prove that \(G\) contains \(k\) disjoint perfect matchings if and only if every set \(X\subseteq V(G)\) contains at least \(k\left(|X|-\frac{1}{2}|V(G)|\right)\) edges. Hint: The most important case is \(k=1\text{.}\)
Let \(G\) be a bipartite graph and let \(b:V(G)\to\mathbb{N}\cup\{0\}\text{.}\) Show that there exists a subgraph of \(G\) in which every vertex \(v\in V(G)\) has degree equal to \(b(v)\) if and only if every set \(X\subseteq V(G)\) contains at least
\begin{equation*}
\frac{1}{2}\left(\sum_{v\in X}b(v) - \sum_{v\in V(G)\setminus X}b(v)\right)
\end{equation*}
edges.
Let \(G\) be a bipartite graph with bipartition \((X,Y)\) and suppose that there is a matching in \(G\) which saturates \(X\text{.}\) Show that, if \(S,T\subseteq X\) such that \(|N(S)|=|S|\) and \(|N(T)|=|T|\text{,}\) then \(|N(S\cap T)|=|S\cap T|\text{.}\)
Let \(G\) be a bipartite graph with no vertices of degree zero and with bipartition \((X,Y)\text{.}\) Suppose that \(d(x)\geq d(y)\) for any vertices \(x\) and \(y\) such that \(x\in X\) and \(xy\in E(G)\text{.}\) Prove that \(G\) has a matching that saturates \(X\text{.}\) Hint: Consider a smallest obstruction to Hall’s Theorem.
-
Let \(X\) be a finite set and let \(W_1,\dots,W_m\) be subsets of \(X\) which we call “winning sets.” Consider the following game. Players 1 and 2 take turns selecting points of \(X\) in such a way that no player can select a point that was selected earlier. As soon as one player has selected all points of one of the winning sets \(W_i\text{,}\) the game ends and that player is the winner. If all points of \(X\) have been selected and no player has won the game, then it is a draw. Note that the game “tic tac toe” has this structure where \(|X|=9\) and there are \(8\) winning sets, each of cardinality three.
For each \(x\in X\text{,}\) let \(w(x)\) be the number of winning sets that \(x\) is contained in. Suppose that the winning sets have the property that if \(x\in W_i\text{,}\) then \(|W_i|\geq 2w(x)\text{.}\) Prove that there exists a strategy for Player 2 which is guaranteed to result in a draw. Hint: Create a bipartite graph where each vertex of \(X\) corresponds to a vertex and each winning set corresponds to two vertices.
Let \(G\) be a bipartite graph with bipartition \((X,Y)\) and let \(b:V(G)\to \mathbb{N}\cup \{0\}\) be a function such that \(\sum_{u\in X}b(u)=\sum_{v\in Y}b(y)\text{.}\) A \(b\)-matching is a function \(M:E(G)\to \mathbb{N}\cup\{0\}\) such that for every \(u\in V(G)\text{,}\)
\begin{equation*}
\sum_{v\in N(u)}M(uv) = b(u).
\end{equation*}
Prove that there exists a \(b\)-matching if and only if every vertex cover \(C\) of \(G\) satisfies
\begin{equation*}
\sum_{v\in C}b(v) \geq \sum_{u\in X}b(u).
\end{equation*}
For \(r\geq1\text{,}\) an \(r\)-uniform hypergraph is a pair \(H=(V,E)\) where \(V\) is a set of vertices and \(E\) is a collection of subsets of \(V\) of cardinality \(r\) called hyperedges. Note that \(2\)-regular hypergraphs are precisely the same thing as graphs. A matching in a hypergraph is a set of disjoint hyperedges and a vertex cover is a set \(S\) of vertices such that every hyperedge \(e\in E\) satisfies \(S\cap e\neq\emptyset\text{.}\) We define the matching number \(\nu(H)\) and vertex cover number \(\tau(H)\) analogously to the case of graphs. Prove that every \(r\)-uniform hypergraph \(H\) satisfies \(\nu(H)\leq \tau(H)\leq r\nu(H)\text{.}\)
Construct a family of examples which shows that the running time for the Gale–Shapley Algorithm can be \(\Omega(n^2)\text{.}\)
Show that there exist instances for the stable marriage problem which have \(\Omega(c^n)\) stable perfect matchings for some \(c>1\text{.}\)
Suppose that \(M_1\) and \(M_2\) are two different stable perfect matchings between companies and interns. Let \(f\) be a function from the interns to the companies such that, for each intern \(i\text{,}\) \(f(i)\) is the company that they are matched to in \(M_1\) or \(M_2\) that they prefer. Show that the set \(M_3=\{if(i): i\text{ is an intern}\}\) is a stable perfect matching.
A bridge in a graph \(G\) is an edge \(e\) such that \(G\setminus \{e\}\) has more components than \(G\text{.}\) Prove that if \(G\) is a \(3\)-regular graph without a bridge, then it has a perfect matching.
Let \(G\) be a graph and let \(X\subseteq V(G)\text{.}\) Prove that there exists a matching in \(G\) saturating every vertex in \(X\) if and only if the number of odd components of \(G\setminus S\) contained in \(T\) is at most \(|S|\) for every \(S\subseteq V(G)\text{.}\)
-
Show that, for any \(n\geq1\text{,}\) there exist instances of the Network Flow Problem having
At least \(n\) different max flows and at least \(n\) different min cuts.
At least \(n\) different max flows and a unique min cut.
A unique max flow and at least \(n\) different min cuts.
Show that the max-flow problem can be reduced to a linear program.
Use linear programming duality to prove the max-flow min-cut theorem.
Show that, for any \(k\geq1\text{,}\) the \(k\)-commodity flow problem can be reduced to a linear program.
Let \(D\) be a digraph and \(s,t\in V(D)\) and let \(f\) be an \((s,t)\)-flow of value \(\alpha\) (for this question, there is no capacity function). Show that there exists an integer valued flow \(g\) with value \(\lceil \alpha\rceil\) such that \(|f(uv)-g(uv)|\leq 1\) for all \(uv\in A(D)\text{.}\)
Prove that if \(G\) is a connected \(k\)-regular bipartite graph, then it is \(2\)-connected.
-
Let \(G\) be a \(2\)-edge connected graph. We define a relation \(\sim\) on the edges of \(G\) where \(e\sim e\) and, for distinct edges, we have \(e\sim e'\) if and only if \(G\setminus\{e,e'\}\) is disconnected.
Prove that \(\sim\) is an equivalence relation.
Prove that, if \(X\) is an equivalence class for \(\sim\text{,}\) then \(G\) contains a cycle that includes all edges of \(X\text{.}\)
Let \(G\) be a graph and let \(D\) be a digraph obtained from orienting the edges of \(G\text{.}\) Prove that, if \(D\) is \(k\)-connected, then \(G\) is \(2k\)-connected.
Let \(G\) be a \(2\)-edge connected graph and let \((S,T)\) be a \(2\)-edge cut in \(G\text{.}\) Let \(u,v\) be the vertices of \(S\) which have neighbours in \(T\) and note that it may be the case that \(u=v\text{.}\) Prove that the graph \(G'\) obtained from \(G[S]\) by adding an edge between \(u\) and \(v\) if they are distinct is \(2\)-edge connected.
Let \(G\) be a graph. Prove that, if \(G\) is \(2\)-connected, then the edges of \(G\) can be oriented to obtain a \(1\)-edge connected digraph (another term for a \(1\)-edge connected digraph is strongly connected).
Let \(s,t\) be vertices in a digraph \(D\text{.}\) Suppose that \(d^+(s)-d^-(s)\geq k\) and that every vertex \(v\in V(D)\setminus\{s,t\}\) satisfies \(d^+(v)=d^-(v)\text{.}\) Prove that there exist \(k\) edge-disjoint paths from \(s\) to \(t\text{.}\)
Suppose that \(G\) is a \(k\)-edge connected graph and let \((S_1,T_1),\dots,(S_m,T_m)\) be \(k\)-edge cuts in \(G\text{.}\) Prove that \(G\setminus\left(\bigcup_{i=1}^m E(S_i,T_i)\right)\) has at most \(2m\) components.
Prove that, if \(G\) is \(k\)-connected, then, for any set \(S\subseteq V(G)\) of cardinality \(k\text{,}\) there exists a cycle in \(G\) containing all vertices of \(S\text{.}\)
A subdivision of a graph \(H\) is a graph obtained from \(H\) by repeatedly inserting vertices in the middle of edges. Prove that if \(G\) is \(k\)-connected and contains a subdivision of the complete graph \(K_{3k}\text{,}\) then, for any distinct vertices \(s_1,\dots,s_k\) and \(t_1,\dots,t_k\) in \(G\) there exist vertex disjoint paths \(P_1,\dots,P_k\) such that \(P_i\) is from \(s_i\) to \(t_i\) for all \(1\leq i\leq k\text{.}\) In other words, for any such graph and a capacity function assigning 1 to every edges, the answer to the “vertex disjoint integer-valued \(k\)-commodity flow problem” is yes.
