= Solution
<Hall marriage theorem> states that a bipartite graph with parts $A,B$ has a matching saturating $A$ iff $|N(S)|\geq|S|$ for every $S\subseteq A$. Starting with a maximum matching, an unmatched vertex and its alternating reachable set would violate Hall unless an augmenting path exists; flipping along that path increases the matching, proving sufficiency.
Every vertex cover meets each edge of a matching, so $γ\leqβ$. Endpoints of a maximal matching cover every edge, so $β\leq2γ$. A disjoint union of $k$ triangles has $(γ,β)=(k,2k)$. For $T_3(30)$, $γ=15$ and $β=30-10=20$. In bipartite graphs the alternating-path proof constructs a cover of size equal to a maximum matching, giving König theorem.
The chromatic index is the minimum number of matchings partitioning the edges. Label vertices of $K_{2^r}$ by the vector space over $\mathbb F_2$; for each nonzero $a$, pair $x$ with $x+a$. These $2^r-1$ perfect matchings partition all edges, while degree gives the matching lower bound, so $χ\prime=n-1$.
Back to article page
