Question 1

Which of the following statements is true? Statement 1: For every graph $G$ and every maximum flow on $G$, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that's possible in the graph. Statement 2: Suppose the maximum $(s,t)$-flow of some graph has value $f$. Now we increase the capacity of every edge by 1. Then the maximum $(s,t)$-flow in this modified graph will have value at most $f + 1$. Consider the following instance of the stable matching problem for 4 men (PQRS) and 4 women (WXYZ). P: W > X > Y > Z\ Q: X > Y > Z > W\ R: W > X > Z > Y\ S: X > Y > W > Z and W: S > Q > R > P\ X: P > S > Q > R\ Y: R > P > Q > S\ Z: R > P > S > Q Consider the following matching: M = {(P, W), (Q, X), (R, Z), (S, Y)}. Which of the following is a blocking pair in the matching above? Consider 4 sets as follows: $W = \{w_1, w_2, w_3\}$, $X = \{x_1, x_2\}$, $Y = \{y_1, y_2, y_3\}$ and $Z = \{z_1, z_2\}$. Suppose we are also given capacity constraints are as follows: $$c(w_2) = c(y_1) = c(y_3) = 1,$$ $$c(w_1) = c(w_3) = c(x_2) = c(y_2) = c(z_1) = 2,$$ $$c(x_1) = c(z_2) = 3$$ $$c(w_i, x_j) = 1, \text{ for all } w_i \in W \text{ and all } x_j \in X,$$ $$c(y_i, z_j) = 1, \text{ for all } y_i \in Y \text{ and all } z_j \in Z$$ $$c(x_1, y_1) = 1, c(x_1, y_2) = 2, c(x_1, y_3) = 1$$ $$c(x_2, y_1) = 0, c(x_2, y_2) = 2, c(x_2, y_3) = 1.$$ Identify the size of a largest collection of 4-tuples from the sets $W, X, Y$ and $Z$ satisfying the given constraints.