2025/06/01 by Chao, Ting-Wei, Dong, Dingding, Xu, Zixuan
#05C80 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2506.01021
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∈ (0,1) in affirmation by proving that G(n,p) is even-degenerate with high probability.