Jaeger's modular orientation conjecture

Jaeger's modular orientation conjecture

Definitions and mathematical statement

Let $k\geq1$ be an integer and $G=(V,E)$ a finite undirected loopless multigraph with at least two vertices. For $\varnothing\neq X\subsetneq V$, let $\delta_G(X)$ denote the set of edges with exactly one endpoint in $X$, counting parallel edges separately. Assume that $G$ is $4k$-edge-connected: \[ |\delta_G(X)|\geq4k \qquad(\varnothing\neq X\subsetneq V). \]

An orientation assigns one direction to each edge. Write $d^+(v)$ for the number directed out of $v$ and $d^-(v)$ for the number directed into $v$. A modular $(2k+1)$-orientation is an orientation for which \[ d^-(v)-d^+(v)\equiv0\pmod{2k+1} \qquad(v\in V). \] The difference need not vanish as an integer; it must be divisible by the indicated odd modulus.

Jaeger's conjecture asserts that every graph satisfying the cut condition has a modular $(2k+1)$-orientation, for every integer $k\geq1$. All edge directions must be chosen together to meet every vertex congruence. There is no choice of variable edge weights in this formulation: each directed edge contributes one at its head and minus one at its tail.

Equivalently, with these fixed unit values the oriented incidence equations vanish in the cyclic group $\mathbb Z/(2k+1)\mathbb Z$. The edge-connectivity hypothesis constrains every cut, rather than only vertex degrees. Neither regularity nor planarity is assumed.

Short English statement

Can every 4k-edge-connected graph be oriented so each vertex has incoming and outgoing degrees congruent modulo 2k+1?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 1 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope.

Reformulating the exact demand.

Source [S2] attributes the conjecture to Jaeger. We investigate prescribed outdegrees rather than replace unit edge contributions by arbitrary nonzero flow values. Put $m=2k+1$. At a vertex of degree $d_v$, an outdegree $a_v$ gives imbalance $d_v-2a_v$. Thus the modular condition is exactly \[ a_v\equiv 2^{-1}d_v\pmod m,\qquad 0\le a_v\le d_v. \] Here $2^{-1}$ exists because $m$ is odd. Choosing an allowed residue at each vertex independently does not yet produce an orientation.

Necessary cut arithmetic.

For $X\subseteq V$, internal edges cancel when vertex imbalances are summed. If $c=|\delta(X)|$ and $b$ cut edges point out of $X$, the sum is $c-2b$. It must be divisible by $m$. In particular an odd cut of size less than $m$ is impossible: its imbalance is odd with absolute value below $m$, and therefore cannot be a multiple of $m$. The proposed $4k=2m-2$ edge-connectivity threshold excludes these small cuts, but the absence of this arithmetic obstruction does not itself make all cut requirements compatible.

A complete orientation criterion for fixed outdegrees.

For integer candidates $a_v$, an orientation with those outdegrees exists if and only if \[ \sum_{v\in V}a_v=|E|,\qquad \sum_{v\in X}a_v\ge |E(G[X])|\quad(X\subseteq V), \qquad a_v\ge0. \] Necessity counts the tails of internal edges. To prove sufficiency, create one left node for each edge and $a_v$ right slots at each vertex $v$. Join an edge node to all slots at its two endpoints. For any set $F$ of edge nodes, let $X$ be its endpoint set. It has $\sum_{v\in X}a_v$ neighbouring slots, at least $|E(G[X])|\ge |F|$. Hall's matching criterion therefore matches every edge to one slot. Orient that edge away from the vertex owning the slot. The total number of slots is $|E|$, so every slot is used and all prescribed outdegrees are attained. Parallel edges are separate left nodes and cause no change in the proof.

The conjecture is consequently reduced to selecting the residues' integer lifts $a_v=r_v+mt_v$ so that all these inequalities hold. The criterion gives an exact certificate and a finite matching algorithm once the lifts are supplied. The unresolved part is choosing them under the stated edge-connectivity hypothesis, not solving the final matching instance.

Two classes and a sharp warning at small connectivity.

If every degree is even, an Euler orientation has equal in- and outdegree at every vertex and works for every $k$, irrespective of connectivity. For two vertices joined by $N$ parallel edges, take $a=N/2$ edges in one direction when $N$ is even. If $N$ is odd and $N\ge m$, take $a=(N-m)/2$. The two imbalances are then $m$ and $-m$. Hence every two-vertex instance with $N\ge4k$ satisfies the conjecture.

At $k=1$, the graph $K_4$ shows why arbitrary cubic graphs cannot replace four-edge-connected graphs. Degree three and modulus three force every vertex to be either a source or a sink. Every edge must join opposite types, which would give a bipartition of $K_4$, an impossibility. Its edge-connectivity is three, below the hypothesis, so this is a threshold warning rather than a counterexample.

Verification and final status.

The root batch script enumerates the $2^6$ orientations of $K_4$ to check the obstruction and verifies the two-vertex formulas for $1\le k\le10$ and $4k\le N\le4k+25$. No numerical test replaces the universal cut criterion. UNRESOLVED. The orientation problem has an exact integer-lift and matching formulation, and two families are proved. We do not establish feasible lifts simultaneously for every subset in an arbitrary $4k$-edge-connected graph.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3217 (OPG-130), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Jaeger's modular orientation conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/jaegers_modular_orientation_conjecture.