An -regular graph with and a bridge in a graph separating an odd number of vertices from the rest cannot have an -colour proper edge colouring. Such a colouring would partition the edges into 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 , every bridge in a graph in an -regular graph automatically has odd-sized sides: if is either resulting connected component of a graph, double counting gives , so parity forces odd. Thus an odd- regular graph with a bridge in a graph is a class two regular graph.
Articles by others on the same topic
There are currently no matching articles.