Even-degeneracy of a random graph

Abstract

A graph is even-degenerate if one can iteratively remove a vertex of even degree at each step until at most one edge remains. Recently, Janzer and Yip showed that the Erdős--Renyi random graph $G(n,1/2)$ is even-degenerate with high probability, and asked whether an analogous result holds for any general $G(n,p)$. In this paper, we answer this question for any constant $p\in (0,1)$ in affirmation by proving that $G(n,p)$ is even-degenerate with high probability.

31 pages. v2, incorporated referee comments