1
$\begingroup$

Let $G$ be bipartite with bipartition $A$, $B$. Suppose that $C$ and C' are both covers of $G$. Prove that $C^{\wedge}$ = (A \cap C \cap C') \cup (B \cap (C \cup C')) is also a cover of $G$.

Does anyone know which theorem is useful for proving this statement?

1 Answers 1

2

This statement is fairly easy to prove without appealing to any special theorems. It might be useful to rewrite the statement

Every edge in $G$ has an endvertex in C''=(A\cap C\cap C')\cup (B\cap(C\cup C'),

which you are trying to prove, as the equivalent statement

If an edge $e\in E(G)$ has no endvertex in B\cap (C\cup C'), then it has an endvertex in A\cap C\cap C'.

Hint: every edge $e$ has an endvertex in $A$, an endvertex in $B$, and at least one endvertex in each of $C$ and C'.

Hope this helps!