= Bridge obstruction to regular edge colouring
An $r$-<regular graph> with $r\geq2$ and a <bridge in a graph> separating an odd number of <vertices> from the rest cannot have an $r$-colour <proper edge colouring>. Such a colouring would partition the <edges> into $r$ <perfect matchings>. Each <perfect matching> must cross the odd-sided <cut of a graph>, so each would have to contain its unique crossing <edge>, the <bridge in a graph>. An <edge> cannot belong to two colour classes.
For odd $r$, every <bridge in a graph> in an $r$-<regular graph> automatically has odd-sized sides: if $S$ is either resulting <connected component of a graph>, <double counting> gives $r|S|=2|E(S)|+1$, so <parity> forces $|S|$ odd. Thus an odd-$r$ <regular graph> with a <bridge in a graph> is a <class two regular graph>.
Back to article page
