Degree sequences realizing labelled $h$-factors

Qinghou Zeng; Zhen Liu

arxiv: 2604.11939 · v1 · submitted 2026-04-13 · 🧮 math.CO

Degree sequences realizing labelled h-factors

Zhen Liu , Qinghou Zeng This is my paper

Pith reviewed 2026-05-10 14:59 UTC · model grok-4.3

classification 🧮 math.CO

keywords degree sequencesH-realizablelabelled h-factorsgraphic sequencesErdős-Gallai theoremspanning subgraphsgraph factors

0 comments

The pith

A degree sequence is H-realizable if and only if it satisfies a generalized Erdős-Gallai inequality for any non-negative integer h.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a necessary and sufficient condition on a non-increasing sequence of integers to be the degree sequence of a graph that contains a particular labelled spanning subgraph H. H is the disjoint union of several cliques, each of size h plus one, that together cover all the vertices. This condition extends the Erdős-Gallai theorem from the case of ordinary graphs to graphs forced to include these cliques, and it confirms a conjecture for the general h. Sympathetic readers would value this because it gives an explicit test for whether a degree sequence can be realized under the structural constraint without constructing the graph itself.

Core claim

We establish a necessary and sufficient condition for a sequence (d1, d2, …, dn) to be H-realizable for any non-negative integer h, thereby confirming a conjecture due to Briggs, McDonald and Shan. Here H is the labelled disjoint union of n/(h+1) cliques of size h+1 each, and realizability means the graph has the given degrees and includes all the edges of H.

What carries the argument

The labelled H, a spanning subgraph consisting of disjoint (h+1)-cliques with vertices grouped in consecutive blocks, which forces a base degree of h on every vertex and limits the possible additional edges to those between different cliques.

Load-bearing premise

The inequality in the condition exactly matches the maximum possible sum of degrees achievable by adding any number of edges between the different cliques while respecting the vertex labels and the forced clique edges.

What would settle it

A concrete non-increasing integer sequence that satisfies the proposed inequality (including even sum and minimum degrees) but for which no graph on the labelled vertices exists that has exactly those degrees and contains all the edges of H.

read the original abstract

For a positive integer $ k $, let $ [k] = \{1, 2, \ldots, k\} $. Let $ h $ be a non-negative integer, and let $ n $ be a multiple of $ h + 1 $. Define $ H $ as the disjoint union of $ n/(h+1) $ cliques (each of size $ h + 1 $) with vertex sets $ V_1, \ldots, V_{n/(h+1)} $, where $ V_i = \{ v_j \mid j = (i-1)(h+1) + k, k \in [h+1] \} $ for $ i \in [n/(h+1)] $. A non-increasing integer sequence $ (d_1, \ldots, d_n) $ is $ H $-realizable if there exists a graph $ G $ with $ V(G) = V(H) = \{ v_i \mid i \in [n] \} $, $ d_G(v_i) = d_i $ for all $ i\in [n] $, and $ G $ contains $ H $ as a spanning subgraph. If $ h = 0 $, then a non-increasing integer sequence $ (d_1, \ldots, d_n) $ is $ H $-realizable if and only if there exists a graph $ G $ with degree sequence $ (d_1, d_2, \dots, d_n) $; Erd\H{o}s and Gallai established a necessary and sufficient condition for this property. Recently, Briggs, McDonald, and Shan extended their result to the case $ h = 1 $. In this paper, we establish a necessary and sufficient condition for a sequence $ (d_1, d_2, \dots, d_n) $ to be $ H $-realizable for any non-negative integer $ h $, thereby confirming a conjecture due to Briggs, McDonald and Shan.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Liu and Zeng prove the general necessary-and-sufficient condition for labelled h-factor degree sequences, confirming the Briggs-McDonald-Shan conjecture via a residual multipartite reduction.

read the letter

Liu and Zeng have established the necessary and sufficient condition for a non-increasing integer sequence to be the degree sequence of a graph containing a specific labelled h-factor as a spanning subgraph. This completes the characterization for arbitrary h and confirms the conjecture posed by Briggs, McDonald, and Shan. The approach is to subtract the h forced intra-clique edges from each degree, reducing the problem to realizing the residual sequence in the complete multipartite graph with m equal parts of size h+1, where m equals n divided by h+1. Necessity comes from a direct count of the maximum possible cross edges under the degree constraints. Sufficiency follows from an inductive construction that respects the fixed partition into cliques. This generalizes the Erdős-Gallai theorem for h=0 and the h=1 case without extra machinery. The proof technique stays combinatorial and avoids circular reasoning or undefined quantities. The soft spots are small. The inequality that results is more complex than the classical one due to the multipartite setting, which might slow down manual checks, but it remains a clear criterion. No unhandled cases or inconsistencies show up in the argument. This work targets specialists in degree sequence realizability and extremal graph theory. Readers who know the prior results for small h will find the full picture useful, as it gives a decision procedure for the constrained graphs. I would bring this to the next reading group because the generalization is straightforward yet complete. It deserves peer review as a resolution of the conjecture with verifiable steps. I would cite it in future work on similar problems.

Referee Report

0 major / 2 minor

Summary. The paper establishes a necessary and sufficient condition on a non-increasing integer sequence (d1,…,dn) with n a multiple of h+1 to be H-realizable, meaning there exists a graph G on the labelled vertex set of H with the given degrees that contains the labelled disjoint union H of m=n/(h+1) cliques of size h+1 as a spanning subgraph. The condition is obtained by subtracting the forced intra-clique edges and requiring the residual sequence to be realizable as a graph inside the complete m-partite graph with equal parts of size h+1. This generalizes the Erdős–Gallai theorem (h=0) and the h=1 case of Briggs–McDonald–Shan, confirming their conjecture for arbitrary h via a direct counting argument for necessity and an inductive construction respecting the part boundaries for sufficiency.

Significance. If the claimed characterization holds, the result supplies a complete, non-circular extension of classical degree-sequence theorems to the setting of graphs forced to contain a specific labelled spanning h-factor. The reduction to residual degrees in a balanced complete multipartite graph, together with the explicit necessity bound on admissible cross edges and the boundary-respecting inductive sufficiency proof, provides a clean combinatorial tool that avoids parameter fitting or circularity. This strengthens the literature on constrained graphic sequences and directly resolves an open conjecture.

minor comments (2)

[Main result] The main theorem statement (presumably in §3) would benefit from an explicit displayed inequality for the residual sequence together with a short worked example for h=2 and n=6 to illustrate the cross-edge bound.
[Introduction] Notation for the vertex labelling of the parts V_i is introduced in the abstract but should be restated once in the introduction before the statement of the conjecture being confirmed.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our manuscript, as well as their assessment of its significance in extending degree-sequence results to labelled h-factors. We appreciate the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; direct generalization of Erdős-Gallai

full rationale

The derivation subtracts the fixed intra-clique edges of H (h per part) from the input sequence and reduces the problem to realizing the residual sequence as a graph on the complete m-partite graph with equal part size h+1. Necessity is obtained by a direct double-counting bound on admissible cross edges; sufficiency proceeds by an inductive construction that respects the labelled parts. Both directions are self-contained combinatorial arguments that do not invoke any fitted parameter, self-defined quantity, or load-bearing citation to prior work by the same authors. The confirmation of the Briggs-McDonald-Shan conjecture is achieved by supplying an independent proof rather than by re-using an unverified self-citation chain. The argument therefore remains non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard axioms of simple graphs, the definition of degree sequences, and the combinatorial counting of possible edges between the fixed cliques; no new entities or fitted constants are introduced.

axioms (2)

standard math Basic properties of simple undirected graphs and non-increasing integer sequences as degree sequences
Invoked throughout the setup and in the generalization of Erdős-Gallai.
standard math The maximum number of edges between two sets of vertices is at most the product of their sizes
Used implicitly when bounding the realizable degrees outside the forced cliques.

pith-pipeline@v0.9.0 · 5671 in / 1383 out tokens · 49311 ms · 2026-05-10T14:59:27.836857+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

R. Brualdi. Problemes combinatoires et th ´eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260, 1978

work page 1976
[2]

A. H. Busch, M. J. Ferrara, S. G. Hartke, M. S. Jacobson, H. Kaul and D. B. West, Packing of graphicn-tuples, J. Graph Theory 70 (2012) 29–39

work page 2012
[3]

Briggs, J

J. Briggs, J. McDonald and S. Shan, Degree sequences realizing labelled perfect matchings, arXiv:2510.01110, 2025

work page arXiv 2025
[4]

Erd ˝os and T

P. Erd ˝os and T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok 11 (1960) 264–274

work page 1960
[5]

J. M. Shook, On a conjecture that strengthens Kundu’sk-factor theorem, J. Graph Theory 108 (2025) 463–491

work page 2025
[6]

Tripathi, S

A. Tripathi, S. Venugopalan and D. B. West, A short constructive proof of the Erd ˝os-Gallai characterization of graphic lists, Discrete Math. 310 (2010) 843–844. 7

work page 2010

[1] [1]

R. Brualdi. Problemes combinatoires et th ´eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260, 1978

work page 1976

[2] [2]

A. H. Busch, M. J. Ferrara, S. G. Hartke, M. S. Jacobson, H. Kaul and D. B. West, Packing of graphicn-tuples, J. Graph Theory 70 (2012) 29–39

work page 2012

[3] [3]

Briggs, J

J. Briggs, J. McDonald and S. Shan, Degree sequences realizing labelled perfect matchings, arXiv:2510.01110, 2025

work page arXiv 2025

[4] [4]

Erd ˝os and T

P. Erd ˝os and T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok 11 (1960) 264–274

work page 1960

[5] [5]

J. M. Shook, On a conjecture that strengthens Kundu’sk-factor theorem, J. Graph Theory 108 (2025) 463–491

work page 2025

[6] [6]

Tripathi, S

A. Tripathi, S. Venugopalan and D. B. West, A short constructive proof of the Erd ˝os-Gallai characterization of graphic lists, Discrete Math. 310 (2010) 843–844. 7

work page 2010