2
$\begingroup$

Could I get some help for part b(i) of below please? Thanks. (Part (a) follows from Hall's Marriage Thm, and b(ii) follows quickly from b(i) I think).

Let $G$ be a bipartite graph with parts $X$ and $Y$ , and with maximum degree $r$.

(a) Let $X_0$ be the set of vertices $x$ in $X$ with degree $d(x) = r$. Show that there is a matching covering $X_0$ (that is, such that each vertex in $X_0$ is incident with an edge in the matching).

(b) Let $X_1 \subseteq X$ and $Y_1 \subseteq Y$ , and suppose that there is a matching $R$ covering $X_1$ and a matching $B$ covering $Y_1$.

  • (i) Consider the subgraph containing just the edges in exactly one of $R$, $B$. Suppose that some component of this subgraph is a path with first edge in $R$ and last edge in $B$. Let $Z$ be the set of vertices in $X_1 \cup Y_1$ on the path. Show that either the edges in $R$ on the path cover $Z$, or the edges in $B$ on the path cover $Z$.
  • (ii) Show that there is a matching in $G$ covering $X_1 \cup Y_1$.
$\endgroup$
2
$\begingroup$

First, let $P$ denote the path and let $x_1, y_1, x_2, y_2, \ldots, x_n, y_n, x_{n+1}$ be the nodes of this path in the order they appear when traversing the path with $x_1, x_2, \ldots, x_{n+1} \in X$ and $y_1, y_2, \ldots, y_n \in Y$. The case that the path does not start in $X$ will be treated at the end.

Since the first edge of the path is in $R$ we know that $x_1 \in X_1$. Since $R$ is a matching we know that the second edge on the path must be in $B$, thus, $y_1 \in Y_1$. Inductively we get that $x_i \in X_1$ and $y_i \in Y_1$ for $i = 1, \ldots, n$.

Assume that $x_{n+1} \in X_1$. Since $R$ is a matching covering $X_1$ there must be an edge $(x_{n+1}, \tilde{y})$ in $R$ covering $x_{n+1}$. Since the path contains only edges which are either in $R$ or in $B$ this edge must be different from $(y_n, x_{n+1})$ which is in $B$. Since $B$ is a matching this edge must be in $R \setminus B$. This contradicts the fact that $(y_n, x_{n+1})$ is the last edge of the path. Thus, we have $x_{n+1} \notin X_1$.

Thereby, taking only edges on the path which are in $R$ covers $x_1, y_1, x_2, y_2, \ldots, x_n, y_n$ which are exactly the nodes in $Z$.

If the path does not start in $X$ then the first node $\bar{y}$ cannot be in $Y_1$: Let $(\bar{y},\bar{x})$ be the first edge on the path and assume that $\bar{y} \in Y_1$. Since the first edge on the path is not in $B$ there must be another edge covering $\bar{y}$ which is in $B$. Since $R$ is a matching this edge cannot be in $R$ because this would result in two edges in $R$ being incident to $\bar{y}$. But then $(\bar{y},\bar{x})$ is not the first edge on the path. Thus, it must hold that $\bar{y} \notin Y_1$. Analogously to the first case, taking only the edges in $B$ on the path covers all nodes in $Z$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.