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?

-

1 Answer

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!

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9597215056419373, "perplexity_flag": "head"}