Even‐Degeneracy of a Random Graph
Abstract
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–Rényi random graph is even‐degenerate with high probability, and asked whether an analogous result holds for any general . In this paper, we answer this question for any constant in affirmation by proving that is even‐degenerate with high probability.
Fields of Study & Subjects
Graph theory and applications
advanced mathematical theories
Topological and Geometric Data Analysis
Publication details
- Journal / source
- Random Structures and Algorithms
- Volume
- 68
- Issue
- 3
- Publication date
- 13 April 2026
- Language
- EN