Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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