Flow polynomial F(G,k): counts nowhere-zero k-flows (edge labelings from Z_k with Kirchhoff conservation at each vertex). F = (-1)^{|E|-|V|+c} T(G;0,1-k). Dual to chromatic polynomial for planar graphs: F(G,k) = P(G*,k)/k.
How to Use
Select graph:
- F(G,k): Flow count
- 5-flow: Conjecture check
- Dual: P(G*,k)
Flow Conjectures
Tutte (1954): every bridgeless graph has a nowhere-zero 5-flow. Proved for 6 (Seymour, 1981). 4-flow conjecture: equiv to four-color theorem for planar. 3-flow conjecture: 4-edge-connected → 3-flow.
Planar Duality
For planar G with dual G*: F(G,k) = P(G*,k)/k. Flows of G = colorings of dual G*! Four-color theorem for planar graphs is equivalent to: every bridgeless planar graph has a nowhere-zero 4-flow.
Step-by-Step Instructions
- 1Select graph.
- 2Compute F(G,k).
- 3Check 5-flow.
- 4Find Tutte connection.
- 5Explore duality.