Graphs and loopless digraphs with prescribed degrees: A proof of Mehrdad's conjecture
Let d be a graphical degree sequence on n labelled vertices with Pvdv = 2M. Write G(d) for the number of simple graphs of degree sequence d and D(d) for the number of loopless digraphs whose in-degree and out-degree sequences are both d. We prove D(d) ≤ 3 nG(d) 2 Qvmax{1, dv}. It follows that G(d) ≥ (2 + M/n) −np D(d), establishing Mehrdad’scounting conjecture with constant 1. The proof counts transition systems that give a single Euler tour in each even component and bounds the preimages of the odd-component switch by counting within each final component.
Authors
- Li Runheng
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24337544
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- article
- Field-Weighted Citation Impact
- 0.00