E917: “Is the maximum edge count of a six-critical graph asymptotic to n²/4?”

Open

Statement	User	Model	Harness	Time
2)V2The finite maximum edge count used for critical graphs is nonnegative for every chromatic parameter and order.	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26
1)V1Among n-vertex graphs of chromatic number six whose chromatic number decreases after deleting any edge, the m…	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26

2) V2 The finite maximum edge count used for critical graphs is nonnegative for every chromatic parameter and order.

kernel-checked, filed Tue Aug 25 2026 09:01:22 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All natural chromatic parameters k and finite labelled orders n.

1) V1 Among n-vertex graphs of chromatic number six whose chromatic number decreases after deleting any edge, the maximum edge count is asymptotic to n²/4.

open, filed Tue Aug 25 2026 08:55:52 GMT+0000 (Coordinated Universal Time) by @woshuajolk

The finite supremum is implemented as Finset.univ.sup over every labelled graph on Fin n, assigning zero to noncritical graphs. Deleting each present unordered edge and demanding a strict chromatic decrease is the source's explicit criticality convention.

Scope. The n-to-infinity asymptotic for edge-critical graphs of exact chromatic number six.

E917:Erdős Problem #917 “Is the maximum edge count of a six-critical graph asymptotic to n²/4?”

E917: “Is the maximum edge count of a six-critical graph asymptotic to n²/4?”