K(3,3) — Proof Output

Step 1

Enumerate all totally cyclic orientations

K(3,3) has 9 edges, so 2⁹ = 512 possible orientations. An orientation is totally cyclic (TCO) if every edge lies in at least one directed cycle. We check all 512 by BFS: for each edge u→v, verify that v can reach u.

Computing all totally cyclic orientations of K(3,3)...
Found 102 TCOs out of 512 total orientations

102 is the right count — it equals the Tutte polynomial evaluation t(K₃₃; 0, 2), the number of strongly connected orientations of K(3,3).

Step 2

Build the full flip graph

For each TCO, find every directed cycle in that orientation. Reversing any one gives another TCO. Build a graph: nodes = 102 TCOs, edges = one cycle reversal apart.

=== All-Cycles Flip Graph ===
Nodes: 102  |  Edges: 210  |  Components: 20
  2× size-6 components, diameters: [1]
  18× size-5 components, diameters: [1]
  Degree range: 4–5, mean 4.12

20 components, each of diameter 1. Diameter 1 means any two TCOs in the same class are connected by a single cycle reversal — they are direct neighbors. The components are small (5 or 6 nodes) and completely connected within themselves.

Step 3

Prove the 20 classes are permanent

Reversing a directed cycle never changes any vertex's out-degree. In a K(3,3) TCO, every vertex has out-degree 1 or 2, and exactly 3 are heavy (out-degree 2). The C(6,3) = 20 ways to assign heavy vertices to 3 of the 6 give exactly 20 permanent classes — no reversal can move between them.

=== Verifying Out-Degree Invariant ===
  ✓ Each component has exactly one out-degree sequence
  ✓ All 20 components have distinct out-degree sequences
  ✓ C(6,3) = 20 = ways to place 3 'heavy' vertices (out=2) among 6 = components

  Heavy vertices on left | # classes | class sizes
  0 left, 3 right       |         1 | [6]
  1 left, 2 right       |         9 | [5, 5, 5, 5, 5, 5, 5, 5, 5]
  2 left, 1 right       |         9 | [5, 5, 5, 5, 5, 5, 5, 5, 5]
  3 left, 0 right       |         1 | [6]

This is Gioan (2007) Proposition 4.10: equivalence classes of the cycle reversing system correspond exactly to indegree sequences. Our 20 classes and their sizes follow from the bipartite symmetry of K(3,3).

Step 4

What happens if you only use the torus face cycles?

K(3,3) embeds on the torus with 3 hexagonal faces. These 3 face cycles (C₆) are geometrically natural. How far do they get you?

=== Face-Cycles-Only Flip Graph (torus faces) ===
Nodes: 102  |  Edges: 24  |  Components: 80
  2× size-3 components, diameters: [1]
  18× size-2 components, diameters: [1]
  60× size-1 components, diameters: [0]
  Degree range: 0–2, mean 0.47
  Isolated nodes (no face cycle available): 60

The 3 torus face cycles are nearly useless: 60 of 102 TCOs have no face cycle available at all, and the flip graph fragments into 80 tiny components. This foreshadows the main result — torus faces never appear in a minimal generating set.

Step 5

Exhaustive search for the minimum generating set

K(3,3) has exactly 15 distinct cycle masks across all 102 TCOs: 9 four-cycles (C₄) and 6 six-cycles (C₆). We check every subset of those 15 — in order of size — and ask: does the restricted flip graph (using only cycles in the subset) have exactly 20 components?

=== Minimum Generator Search ===
Distinct cycle masks: 15 (9 C4, 6 C6)
  Size 1: checked    15 subsets → 0 generating sets (0 C4-only)
  Size 2: checked   105 subsets → 0 generating sets (0 C4-only)
  Size 3: checked   455 subsets → 0 generating sets (0 C4-only)
  Size 4: checked  1365 subsets → 0 generating sets (0 C4-only)
  Size 5: checked  3003 subsets → 9 generating sets (9 C4-only)
  ✓ Minimum generating set size = 5

Zero subsets of size ≤ 4 work — no exceptions. This is a complete proof by exhaustive search: all C(15,1) + C(15,2) + C(15,3) + C(15,4) = 1940 subsets of size ≤ 4 were checked. The cycle rank of K(3,3) is E−V+1 = 4. The minimum is 5 — one more.

Step 6

The 9 minimal generating sets

Label the 9 four-cycles by which pair of left vertices and which pair of right vertices they connect. The grid below names them a–i:

         R₀R₁   R₀R₂   R₁R₂
L₀L₁  [  a  ] [  b  ] [  c  ]
L₀L₂  [  d  ] [  e  ] [  f  ]
L₁L₂  [  g  ] [  h  ] [  i  ]

The 9 minimal generating sets (each is 5 of the 9 four-cycles):

  Set 1:  a b ·  d e ·  · · i   →  { a, b, d, e, i }
  Set 2:  · · c  d e ·  g h ·   →  { c, d, e, g, h }
  Set 3:  a · c  d · f  · h ·   →  { a, c, d, f, h }
  Set 4:  · b ·  d · f  g · i   →  { b, d, f, g, i }
  Set 5:  · b c  d · ·  · h i   →  { b, c, d, h, i }
  Set 6:  a · c  · e ·  g · i   →  { a, c, e, g, i }
  Set 7:  a · ·  · e f  · h i   →  { a, e, f, h, i }
  Set 8:  · b c  · e f  g · ·   →  { b, c, e, f, g }
  Set 9:  a b ·  · · f  g h ·   →  { a, b, f, g, h }