= Solution
{c}
A <proper edge colouring> assigns colours to the <edges> of a <graph> so that distinct <edges> sharing a <vertex> have different colours. The <edge chromatic number> $\chi'(G)$ is the least number of colours in such an assignment. Equivalently, it is the least number of <matchings in a graph> whose disjoint union is the entire collection of <edges>.
<Vizing's theorem> states that a finite <simple graph> of <maximum degree> $\Delta$ satisfies
$$
\boxed{\Delta\leq\chi'(G)\leq\Delta+1.}
$$
The lower bound holds because all <edges> incident with a <vertex> of <vertex degree> $\Delta$ require different colours.
<Hall's marriage theorem> states that a finite <bipartite graph> with <vertex sets> $A,B$ has a <matching in a graph> saturating $A$ if and only if
$$
\boxed{|N(S)|\geq|S|\quad\text{for every }S\subseteq A,}
$$
where $N(S)\subseteq B$ is the <graph neighbourhood> of $S$. Here <matching saturation> means that each <vertex> of $A$ is incident with an <edge> of the <matching in a graph>; it does not require every <vertex> of $B$ to be met.
Back to article page
