# Bipartite graph cover problem

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?

-

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!

-