Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

This paper presents two counterexamples to K. Jain's second conjecture regarding unit vector flows on graphs, demonstrating that specific point sets on a sphere require values outside the proposed range of $\{-4, \dots, 4\}$, thereby challenging a potential pathway to proving Tutte's 5-flow conjecture.

The Gist

Imagine you are a city planner trying to design a traffic system for a network of roads (a graph). The goal is to keep traffic flowing smoothly without any dead ends (bridges) where cars get stuck.

In the world of math, there's a famous puzzle called Tutte's 5-Flow Conjecture. It basically asks: "Can we always assign a number between 1 and 4 to every road in a network so that traffic balances perfectly at every intersection?"

The conjecture is widely believed to be true and remains so. And to prove it, a brilliant mathematician named K. Jain proposed a two-step plan involving a giant, invisible sphere (like a globe) floating in space.

The Two-Part Plan (Jain's Conjectures)

Jain suggested that if we could solve two specific puzzles on this sphere, we would automatically solve the traffic puzzle for the whole world.

1. The Flow Puzzle: Can we draw arrows on every road of any network, where each arrow points to a spot on the surface of a sphere? (This is the "Unit Vector Flow").
2. The Labeling Puzzle: Can we paint the entire surface of that sphere with numbers from -4 to +4 (skipping zero) such that:
   • Opposite sides of the sphere (North Pole vs. South Pole) have opposite numbers (e.g., +3 and -3).
   • If you pick any three points that form a perfect triangle on a great circle (like the equator), their numbers add up to zero.

If both of these were true, the big traffic puzzle (Tutte's 5-Flow) would be solved.

The Plot Twist: The Paper's Discovery

The author of this paper, Nikolay Ulyanov, says: "Hold on. The second part of the plan is broken."

He found two specific "landmarks" on the sphere where it is impossible to paint them with numbers only from -4 to +4 while following the rules. To make the math work for these specific spots, you are forced to use the number 5 (or -5).

Think of it like a game of Musical Chairs with strict rules:

• The Rules: You have 8 chairs (numbers -4, -3, -2, -1, 1, 2, 3, 4). You have to seat 50 people (points on the sphere) such that opposite people sit in opposite chairs, and any trio sitting in a circle must have their chair numbers sum to zero.
• The Problem: Ulyanov built two specific arrangements of people (one with 50 people, one with 36) where, no matter how you try, you run out of chairs. You must bring in a 9th chair (the number 5) to make the math balance.

The Two Counterexamples

The paper presents two "impossible" maps:

1. The 50-Point Expansion (The "Icosidodecahedron"):
   Imagine a soccer ball made of 30 points. Ulyanov took this shape and "inflated" it. He added new points around the original ones, creating a complex web of 50 points. When he tried to apply the -4 to +4 rule, the math crashed. The only way to fix the balance was to use the number 5.

2. The 36-Point Construction (The "Square Root" Puzzle):
   This one is a bit more abstract. He used a recipe involving square roots (like $\sqrt{3}$) to generate 36 specific points on the sphere. Even though this group is smaller, it's just as stubborn. It refuses to be labeled with numbers up to 4. It demands a 5.

Why Does This Matter?

You might ask, "So what? We just need to use 5 instead of 4?"

Here is the catch:

• Jain's Plan was a shortcut. He thought, "If we can label the sphere with numbers up to 4, then the traffic puzzle is solved with numbers up to 5."
• The Reality: Because the sphere sometimes needs a 5 to be labeled, Jain's shortcut doesn't work. It doesn't prove that the traffic puzzle is solvable with numbers up to 5. It leaves the door open that maybe some traffic networks do need a 6, or maybe they still only need a 5, but we can't prove it using this specific sphere method.

The Bottom Line

The paper is like a detective story where the detective (Ulyanov) finds a flaw in the master plan.

• The Master Plan: "If we can solve the Sphere Puzzle with small numbers, we solve the Traffic Puzzle."
• The Detective's Finding: "The Sphere Puzzle actually requires a bigger number (5) for some tricky configurations. Therefore, the Master Plan is invalid."

The paper doesn't say the Traffic Puzzle is impossible to solve; it just says this specific shortcut doesn't work. Now, mathematicians have to go back to the drawing board to find a new way to prove that every bridgeless network can indeed be managed with just five traffic lights.

In short: The author found two "stubborn" shapes on a sphere that refuse to follow the rules of the proposed plan, proving that the plan itself is flawed.

Technical Summary

1. Problem Statement

The paper addresses two interconnected conjectures proposed by K. Jain regarding unit vector flows on graphs and their relationship to Tutte's 5-flow conjecture.

• Conjecture 1.1 (Unit Vector Flows): Every bridgeless graph admits a flow where each edge is assigned a vector from the 2-dimensional unit sphere $S^2$ (a nowhere-zero 3-dimensional flow).
• Conjecture 1.2 ($S^2$ nz5-flow): There exists a mapping $q: S^2 \to \{-4, -3, -2, -1, 1, 2, 3, 4\}$ such that:
  1. Antipodal points sum to zero ($q(-x) = -q(x)$).
  2. Any three points equidistant on a great circle sum to zero ($q(a) + q(b) + q(c) = 0$).
• The Implication: If both Conjecture 1.1 and 1.2 are true, they would jointly imply Tutte's 5-flow Conjecture (that every bridgeless cubic graph has a nowhere-zero 5-flow).

The specific focus of this paper is to disprove Conjecture 1.2 by demonstrating that no such mapping exists for certain finite subsets of $S^2$. Specifically, the author shows that for certain configurations, the constraints force the use of values $\pm 5$, meaning a nowhere-zero 6-flow is required, and a nowhere-zero 5-flow is impossible.

2. Methodology

The author employs a combination of geometric construction and computational verification via Boolean Satisfiability (SAT) solving.

A. Geometric Construction

The paper constructs finite subsets of points on the unit sphere $S^2$ designed to maximize the constraints of "great-circle triples" (three points on a great circle that are equidistant).

1. Counterexample 1 (50-point set):

   • Based on the Icosidodecahedron (30 points).
   • The construction expands the icosidodecahedron by placing small circles around each vertex and intersecting them based on specific spherical distances ($2\pi/5$).
   • This results in a set of 50 points with 40 great-circle triples.
   • The coordinates involve the golden ratio $\phi$ and specific algebraic scaling factors.
   • Topologically, this structure relates to the Petersen graph and a Möbius ladder.

2. Counterexample 2 (36-point set):

   • Based on square root arithmetic.
   • Coordinates are generated using linear combinations of $\sqrt{1}$ and $\sqrt{3}$, normalized to the unit sphere.
   • The author generates a large candidate set, iteratively prunes points that do not participate in multiple triples, and converges on a minimal connected component of 36 points and 13 triples.

B. Computational Verification (SAT Solving)

To prove that no valid labeling exists for these sets using only values $\{-4, \dots, 4\}$:

• Encoding: The problem is encoded as a Boolean Satisfiability (SAT) instance.
  • Variables represent the assignment of values $\{-4, \dots, 4\}$ to each point.
  • Constraints include:
    • Exactly-one: Each point gets exactly one value.
    • Antipodal: $q(-p) = -q(p)$.
    • Triple-sum: $q(a) + q(b) + q(c) = 0$ for every great-circle triple.
• Solvers: The resulting CNF formulas were fed into PicoSAT and pycosat.
• Formal Verification: The results were cross-validated using Lean 4 with the bv_decide tactic to ensure mathematical rigor.

3. Key Contributions and Results

Disproof of Conjecture 1.2

The paper provides two definitive counterexamples to Jain's second conjecture:

1. The 50-point Icosidodecahedron Expansion:

   • The SAT solver determined the CNF formula (200 variables, 19,765 clauses) is unsatisfiable.
   • This proves that no labeling exists using only $\{\pm 1, \dots, \pm 4\}$.
   • A valid labeling exists if the range is expanded to $\{\pm 1, \dots, \pm 5\}$ (a nowhere-zero 6-flow).

2. The 36-point Square Root Construction:

   • The SAT solver determined the CNF formula (144 variables, 6,710 clauses) is unsatisfiable.
   • Like the first example, this set requires values $\pm 5$ to satisfy the constraints.
   • A valid labeling exists for the range $\{\pm 1, \dots, \pm 5\}$.

Structural Insights

• The paper clarifies the relationship between the Icosidodecahedron, the Petersen graph, and the Möbius ladder in the context of flow constraints.
• It demonstrates that while the Petersen graph admits a nowhere-zero 5-flow (integer values), the geometric realization of its vertices on $S^2$ with the specific "great circle" constraints forces a higher flow number (6-flow) when restricted to the specific algebraic structure of the sphere.

4. Significance and Future Directions

• Impact on Tutte's Conjecture: Since Conjecture 1.2 is false, the specific path of combining Jain's two conjectures to prove Tutte's 5-flow conjecture is broken. The paper suggests that a different subset of $S^2$ (possibly infinite or with specific algebraic properties) might be needed to salvage the proof strategy for Tutte's conjecture.
• Flow vs. Mod-k Flow: The author notes an empirical observation that for the tested subsets, the minimal $k$ required for a nowhere-zero $k$-flow is identical to that of a nowhere-zero mod-$k$ flow. The paper raises the question of whether this equivalence holds universally.
• Open Questions:
  • Can a subset be found that requires values $\pm 6$ or higher?
  • What is the minimal size of a counterexample set?
  • Can a "nice" subset (e.g., with algebraic coordinates) be found that admits a 5-flow to support Tutte's conjecture?

Conclusion

Nikolay Ulyanov successfully disproves Jain's second conjecture by constructing two finite subsets of the unit sphere where the geometric constraints of great-circle triples make a nowhere-zero 5-flow impossible. The work relies on sophisticated geometric constructions and rigorous SAT-based verification, shifting the focus of research toward finding alternative geometric structures that might still support Tutte's 5-flow conjecture.