Question bank — Bipartite graphs — 2-coloring test, bipartite matching — Hopcroft-Karp

False — any odd cycle blocks bipartiteness. The pentagon $C_5$ is triangle-free yet cannot be 2-colored, so "no triangle" is weaker than "no odd cycle".

True — a tree has no cycles at all, so certainly no odd cycle; you can 2-color it by parity of depth (see BFS / DFS traversal).

True — this is the defining theorem. Even cycles alternate colors and close consistently; an odd cycle forces the start vertex to be both colors.

False — an edge inside one side ($L$–$L$ or $R$–$R$) creates a same-color edge, i.e. an odd cycle, breaking bipartiteness.

True — bipartiteness is checked per component; if every component is 2-colorable the whole graph is bipartite (color each component independently).

True — with no edges there is no constraint to violate; you may put all vertices in $L$ and $R$ empty, and every edge (none) trivially crosses.

False — the size is unique, but many different edge sets can achieve it (e.g. a 4-cycle has two distinct perfect matchings).

False — it finds a maximum matching. If no perfect matching exists (e.g. more left vertices than can be covered), it returns the largest possible, which may leave vertices unmatched.

False — König's Theorem holds only for bipartite graphs. For general graphs min vertex cover can exceed max matching (a triangle has matching 1, cover 2).

True — it sometimes does, but not reliably; greedy gives a maximal matching (no free edge addable) which can be strictly smaller than maximum.

True — the shortest augmenting-path length strictly increases each phase, and a counting argument bounds the total phases by $O(\sqrt{V})$.

Error: you only tested one component. You must loop over all uncolored vertices and restart BFS/DFS for each, or unreached components go unchecked.

Error: the rule is $\text{color}[v]=1-\text{color}[u]$ (opposite). Copying the color would put same colors on an edge — the exact thing bipartiteness forbids.

Error: it starts and ends at unmatched (free) vertices; that's what lets a flip increase the matching by exactly one.

Error: you flip every edge on the path — matched become unmatched and vice versa. Since there is one extra unmatched edge, the net gain is $+1$.

Error: one phase finds a maximal set of shortest, vertex-disjoint augmenting paths only. Longer paths are handled in later phases as the shortest length grows.

Error: both compute the same maximum size (guaranteed by Berge's Theorem); they only differ in speed — $O(VE)$ versus $O(E\sqrt{V})$.

Error: that is maximal, not maximum. An augmenting path may re-route existing edges to reach size 4 without simply "adding" an edge.

Colors must alternate B,W,B,W,… along the cycle. Returning to the start after an odd number of steps demands the opposite of the start color, contradicting the start's own color.

It alternates unmatched, matched, unmatched, … starting and ending with unmatched edges, so it has $k$ matched and $k+1$ unmatched edges — total $2k+1$, always odd.

It batches many shortest augmenting paths per phase, forcing the shortest length to strictly increase, which caps phases at $O(\sqrt{V})$; each phase is one $O(E)$ BFS+DFS sweep.

BFS builds the layered graph of shortest augmenting distances; DFS alone finds some path but not the shortest, losing the length-increase guarantee that gives the $\sqrt{V}$ bound.

Alternating paths never form odd "blossoms" in bipartite graphs, so plain BFS/DFS augmentation works; general graphs need the Blossom Algorithm to contract odd cycles.

Add a source into $L$ and a sink out of $R$, all capacities 1; an integer max flow saturates a maximum set of disjoint $L$–$R$ edges, which is exactly a maximum matching (see Maximum Flow).

Because max independent set $=V-$ (max matching) in bipartite graphs; once Hopcroft–Karp gives the matching size, subtraction gives the answer instantly.

Yes — put it in $L$ (or $R$); with no edges there is nothing to violate. Its maximum matching is size 0.

Yes — even cycles alternate colors and close consistently. Its two color classes are the alternating vertices.

No — the loop's two endpoints are the same vertex, so it can never straddle $L$ and $R$; it acts like a length-1 odd cycle.

Size 1 — the shared right vertex can be matched to at most one of them (matchings share no endpoints), leaving the other left vertex unmatched.

No — a perfect matching would need every vertex matched, but the smaller side runs out; the max matching size is capped by $\min (|L|,|R|)$ (and possibly less).

Size 0 — with no edges there is nothing to match; Hopcroft–Karp's first BFS finds no augmenting path and stops immediately.

Exactly 2 if and only if the graph is bipartite (and has at least one edge); non-bipartite graphs need 3 or more, so 2-coloring is the special easy case.