Heredity properties of connectedness in edge-coloured complete graphs Original Research Article

If the monochromatic graphs G1 and G2 in a 2-edge-coloured complete graph Km (m⩾6) are connected, then there exist at least two vertices x such that the graphs G1⧹x and G2⧹x are also connected. Similar theorems are proved for k-edge-coloured complete graphs. They generalize earlier results of Idzik et al. [Discrete Math. 66 (1987) 119–125]. Examples are shown that analogous theorems are no longer true for 3-uniform complete hypergraphs.