The Probability That a Random Graph is Even‐Decomposable

ABSTRACT A graph with an even number of edges is called even‐decomposable if there is a sequence such that for each , has an even number of edges and is an independent set in . The study of this property was initiated recently by Versteegen, motivated by connections to a Ramsey‐type problem and questions about graph codes posed by Alon. Resolving a conjecture of Versteegen, we prove that all but an proportion of the ‐vertex graphs with an even number of edges are even‐decomposable. Moreover, answering one of his questions, we determine the order of magnitude of the smallest for which the probability that the random graph is even‐decomposable (conditional on it having an even number of edges) is at least . We also study the following closely related property. A graph is called even‐degenerate if there is an ordering of its vertices such that each has an even number of neighbours in the set . We prove that all but an proportion of the ‐vertex graphs with an even number of edges are even‐degenerate, which is tight up to the implied constant.