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$
1
$\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