Amalgamations of almost regular edge-colourings of simple graphs

A finite graph F is a detachment of a finite graph G if G can be obtained from F by partitioning V(F) into disjoint sets S₁, …, S_n and identifying the vertices in S_i to form a single vertex α_i for i = 1, …, n. Thus E(F) = E(G) and an edge which joins an element of S_i to an element of S_j in F will join α_i to α_j in G. If L is a subset of E(G) then G(L) denotes the subgraph of G such that V(G(L)) = V(G), E(G(L)) = L. We call a graph almost regular if there is an integer d such that every vertex has valency d or d + 1. Suppose that E(G) is partitioned into disjoint sets E₁, …, E_r. Hilton 3] found necessary and sufficient conditions for the existence of a detachment F of G such that F is a complete graph with 2r + 1 vertices and F(E_i) is a Hamilton circuit of F for i = 1, …, r. We give a new proof of Hilton's theorem, which also yields a generalisation. Specifically, for any q ∈ {0, 1, …, r}, we find necessary and sufficient conditions for G to have a detachment F without loops or multiple edges such that F(E₁), …, F(E_r) are almost regular and F(E₁), …, F(E_q) are 2-edge-connected and each vertex ξ of G arises by identification from a prescribed number g(ξ) of vertices of F.