Edge colouring number of a k-regular graph and relation to bridges

Question

I am researching graph theory, and am confused about this problem. I am considering a $k$-regular connected graph $G$, where $k\geq2$ and where $\chi'(G)=k$ (the edge colouring number.) I then want to be able to show that $G$ does not contain any bridges.

However, I do not know how to solve this. I can show that as, $\chi'(G)=k$, the edge colouring number is the same as the maximum degree of a vertex, there must be an even number of vertices in $G$. But this does not tell me whether $k$ must be odd or even. I feel like I want to remove the bridge, and then use the handshaking lemma to show that for one of the new connected subgraphs formed by removing the bridge the equality does not match, as one side is odd and the other even, but I cannot seem to gather the right information to do this. Or perhaps this is the wrong method.

Any help appreciated.

Answer 1

Note with an edge colouring $k$, you can find $k$ distinct perfect matchings, one for each colour class.

• Suppose a bridge $uv$ exist, then the removal of this bridge gives two distinct components, say $C_1$ and $C_2$.

• Next, we note that the union of two disjoint perfect matchings form a disjoint union of cycle that spans the graph.

• Now, pick two colour classes, one of which contains $uv$, and there must be a cycle between $u$ and $v$.

• However, this meant that either

  • $uv$ has a loop (contradicting $uv$ bridge as the other edge still connects the two components)
  • Or that some vertex in $C_1$ must be connected to some other vertex in $C_2$ to close the loop.
• This contradicts $C_1$ and $C_2$ being two distinct components, and we are done.