Even-degeneracy of a random graph
Pith reviewed 2026-05-19 12:08 UTC · model grok-4.3
The pith
Random graphs G(n,p) for constant p are even-degenerate with high probability.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that G(n,p) is even-degenerate with high probability for any constant p in (0,1). This means there exists, with probability tending to one, a vertex ordering such that each vertex has even degree in the subgraph induced by the vertices not yet removed at the moment it is deleted, and the process continues until the remaining graph has at most one edge.
What carries the argument
The even-degeneracy property, defined as the ability to iteratively remove vertices of even degree until at most one edge remains.
If this is right
- The removal process succeeds without becoming stuck in an all-odd-degree core with multiple edges remaining.
- The property holds for every fixed edge probability rather than only special values.
- Degree concentration in the binomial model guarantees an even-degree vertex is available at each step with high probability.
Where Pith is reading between the lines
- Similar removal sequences might exist in random graphs whose edge probability changes slowly with n.
- Direct sampling of moderate-sized instances could give numerical evidence on how quickly the success probability approaches one.
- The parity-based ordering may relate to questions about Eulerian paths or orientations in random subgraphs.
Load-bearing premise
The assumption that the iterative removal process never becomes trapped in a remaining subgraph that has more than one edge and only odd-degree vertices.
What would settle it
A concrete counterexample would be a single sample from G(n,p) for large n and fixed p in which, after removing every available even-degree vertex, the leftover graph still contains more than one edge and every vertex has odd degree.
read the original 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\H{o}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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the Erdős–Rényi random graph G(n,p) is even-degenerate with high probability for every constant p ∈ (0,1). Even-degeneracy is defined as the existence of an ordering in which each vertex has even degree in the induced subgraph on the remaining vertices at the moment of its removal, continuing until at most one edge is left. The argument extends the Janzer–Yip result from the p = 1/2 case by analyzing an iterative removal process and controlling the probability that the process becomes trapped before reaching a single edge or empty graph.
Significance. If the central claim holds, the result establishes that even-degeneracy is a robust property of dense random graphs across the full range of constant edge probabilities. This strengthens the structural understanding of G(n,p) and may inform algorithms that rely on degree-parity or degeneracy orderings. The proof appears to combine standard binomial concentration with a careful accounting of the removal dynamics.
major comments (1)
- The analysis of the iterative removal process must separately control the regime in which the remaining vertex set has size m = O(1) or o(log n). For p ≠ 1/2 the probability that a vertex has even degree in the induced G(m,p) equals [1 + (1−2p)^{m−1}]/2, which deviates from 1/2 by an exponentially small but non-negligible bias when m is bounded. If the argument adapts the Janzer–Yip concentration without an explicit union bound or exhaustive check over potential small induced subgraphs that consist entirely of odd-degree vertices and contain more than one edge, the whp success of the process is not yet guaranteed for general p.
minor comments (1)
- The abstract should state the precise probability bound (e.g., 1 − o(1)) rather than the informal phrase “with high probability.”
Simulated Author's Rebuttal
We thank the referee for the careful reading and for identifying the need for an explicit treatment of the small-vertex-set regime when p ≠ 1/2. We agree that this case requires separate control and will revise the manuscript to incorporate it.
read point-by-point responses
-
Referee: The analysis of the iterative removal process must separately control the regime in which the remaining vertex set has size m = O(1) or o(log n). For p ≠ 1/2 the probability that a vertex has even degree in the induced G(m,p) equals [1 + (1−2p)^{m−1}]/2, which deviates from 1/2 by an exponentially small but non-negligible bias when m is bounded. If the argument adapts the Janzer–Yip concentration without an explicit union bound or exhaustive check over potential small induced subgraphs that consist entirely of odd-degree vertices and contain more than one edge, the whp success of the process is not yet guaranteed for general p.
Authors: We agree that the bias term (1−2p)^{m−1} is non-negligible for bounded m and that the Janzer–Yip concentration argument, which relies on exact 1/2 probabilities, must be supplemented for general constant p. The current manuscript adapts the iterative removal framework but does not yet contain an explicit union bound or case analysis for the o(log n) regime. We will add a new lemma that performs a direct union bound over all vertex subsets of size at most C log n. For each fixed m the probability that a given m-set induces a graph with all degrees odd and at least two edges is at most 1−δ for some δ>0 depending only on p and m; multiplying by the at most n^m choices of the set and summing over m ≤ C log n produces an o(1) failure probability. This complements the large-set concentration and guarantees that the removal process reaches a single edge or the empty graph with high probability. revision: yes
Circularity Check
No circularity; derivation relies on independent concentration analysis
full rationale
The paper proves even-degeneracy of G(n,p) for constant p by extending the Janzer-Yip argument via direct analysis of an iterative vertex-removal process. It invokes standard binomial concentration bounds and parity-control lemmas that are derived from the G(n,p) model itself rather than fitted to the target conclusion or reduced to a self-citation chain. No step equates a claimed prediction to an input parameter by construction, and the cited prior result for p=1/2 is external and non-overlapping in authorship. The argument remains self-contained against external probabilistic benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Binomial degree distributions in G(n,p) concentrate sufficiently to guarantee even-degree vertices exist at each removal step.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.