TOPICS
Search

Graphic Additive Base Conjecture


The graphic additive base conjecture asserts that, for an odd prime q, the presence of q edge-disjoint spanning trees allows every compatible prescription of outdegrees modulo q to be realized by a graph orientation.

Jafari (2026) proved the stronger statement for every integer q>=2. If a connected multigraph G=(V,E) has q edge-disjoint spanning trees and h:V->Z/qZ satisfies

 sum_(v in V)h(v)=|E|  (modq),

then G has a graph orientation with d^+(v)=h(v)  (modq) for every v in V. Here d^+(v) is the outdegree; loops are permitted and contribute one to the outdegree.

The revised argument also gives decomposition and flow consequences. Every simple graph with q edge-disjoint spanning trees and an edge count divisible by q decomposes into star graphs K_(1,q), for integers q>=2. In particular, 2q-edge connectivity suffices. For q=2, connectedness and an even edge count suffice. Jafari (2026) also proved the sharp strict circular flow number bound F_c(G)<2+1/k for every (4k+2)-edge-connected multigraph and integer k>=1.


See also

Graph Orientation, Outdegree, Spanning Tree

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Jafari, A. "Graphic Additive Bases and Graph Flows." 16 Oct 2026. https://arxiv.org/abs/2610.07034v3.

Cite this as:

Weisstein, Eric W. "Graphic Additive Base Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphicAdditiveBaseConjecture.html

Subject classifications