Supereulerian complementary graphs

Nebeský in [12] show that for any simple graph with n ≥ 5 vertices, either G or G c contains an eulerian subgraph with order at least n ‐ 1, with an explicitly described class of exceptional graphs. In this note, we show that if G is a simple graph with n ≥ 61 vertices, then either G or G c is supereulerian, with some exceptions. We also characterize all these exceptional cases. These results are applied to show that if G is a simple graph with n ≥ 61 vertices such that both G and G c are connected, then either G or G c has a 4‐flow, or both G and G c have cut‐edges. © 1993 John Wiley & Sons, Inc.