[#P23] Hadwiger's conjecture

Problem. Every finite graph \(G\) with chromatic number \(\chi(G)=k\) contains the complete graph \(K_k\) as a minor.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

The conjecture connects vertex coloring to graph minors and contains the four-color theorem as a special case.

2Definitions

Definition 1 (The chromatic number). The chromatic number is the smallest number of colors needed to color vertices so that adjacent vertices receive different colors.

Definition 2 (A graph minor). A graph minor is obtained by deleting vertices or edges and contracting edges.

3What counts as a solution

Prove the clique-minor conclusion for every finite graph, or give a finite graph whose chromatic number exceeds the order of its largest complete minor.

1Status

Saved packet · July 31, 2026

What counts as a solution

Saved packet status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: The conjecture is proved through the cases equivalent to at most six colors. The linked 2025 article proves a triangle-free minor-avoiding independence result and still treats the general finite-graph statement as open. Exact unresolved remainder: Prove that every finite graph has a complete minor of order at least its chromatic number, or give a finite graph whose chromatic number exceeds its largest complete minor.^[1][2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
Unresolved in this packet after the dated source check. Strongest checked result: The conjecture is proved through the cases equivalent to at most six colors. The linked 2025 article proves a triangle-free minor-avoiding independence result and still treats the general finite-graph statement as open. Exact unresolved remainder: Prove that every finite graph has a complete minor of order at least its chromatic number, or give a finite graph whose chromatic number exceeds its largest complete minor.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 Unresolved in this packet after the dated source check. Strongest checked result: The conjecture is proved through the cases equivalent to at most six colors. The linked 2025 article proves a triangle-free minor-avoiding independence result and still treats the general finite-graph statement as open. Exact unresolved remainder: Prove that every finite graph has a complete minor of order at least its chromatic number, or give a finite graph whose chromatic number exceeds its largest complete minor.^[1][2] Relevance to this problem For Hadwiger's conjecture, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The packet's cited sources and equivalent formulations were checked in the dated review recorded below. Strongest checked result: The conjecture is proved through the cases equivalent to at most six colors. The linked 2025 article proves a triangle-free minor-avoiding independence result and still treats the general finite-graph statement as open. Exact unresolved remainder: Prove that every finite graph has a complete minor of order at least its chromatic number, or give a finite graph whose chromatic number exceeds its largest complete minor. Open full record →
Prove the clique-minor conclusion for every finite graph, or give a finite graph whose chromatic number exceeds the order of its largest complete minor.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 Prove the clique-minor conclusion for every finite graph, or give a finite graph whose chromatic number exceeds the order of its largest complete minor.^[1] Relevance to this problem For Hadwiger's conjecture, record hadwiger-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Prove the clique-minor conclusion for every finite graph, or give a finite graph whose chromatic number exceeds the order of its largest complete minor. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Prove the clique-minor conclusion for every finite graph, or give a finite graph whose chromatic number exceeds the order of its largest complete minor. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Open full record →
No records match these filters.

Notes and companion material

Original intake status. The cited 2025 AMS article calls Hadwiger's conjecture celebrated and treats it as unresolved. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.

The conjecture is known for chromatic number at most 6. General cases require attention to the distinction between subgraphs, subdivisions, and minors.

Recorded example 1. A complete graph K_k has chromatic number k and contains itself as a K_k minor.

Computational notes

Exhaustive graph generation can verify bounded orders without settling the universal statement.

2See also

A period-six recurrence for domination on the three-row knight graphgraph theory
Leaf complexity of six-vertex graph connectivitygraph theory
Exact Hamiltonicity probability on eight labeled verticesgraph theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Hadwiger's conjecture.” TheoremDB. P23. Problem statement; statement text SHA-256 88978ab49684ebd1184ea95ed4103eeba4bf724ee9e5e5718f67326550f045c4. https://theoremdb.org/statement/?ref=P23

BibTeX

@misc{theoremdb-problem-88978ab49684ebd1184ea95ed4103eeba4bf724ee9e5e5718f67326550f045c4,
  title = {{Hadwiger's conjecture}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 88978ab49684ebd1184ea95ed4103eeba4bf724ee9e5e5718f67326550f045c4},
  url = {https://theoremdb.org/statement/?ref=P23}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from ams.org^[1], current as of July 31, 2026.

1Lean verification

1References

Packet source. Independence number in triangle-free graphs avoiding a clique minor. Zdenek Dvorak and Liana Yepremyan, Proceedings of the American Mathematical Society 153 (2025), abstract and introduction. Zdenek Dvorak and Liana Yepremyan, Proceedings of the American Mathematical Society 153 (2025), abstract and introduction. ↗website · primary source · checked 2026-07-31Source use: original summary.The cited 2025 AMS article calls Hadwiger's conjecture celebrated and treats it as unresolved. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Hadwiger's conjecture, the reviewed source scope is Zdenek Dvorak and Liana Yepremyan, Proceedings of the American Mathematical Society 153 (2025), abstract and introduction. The packet makes no inference beyond that cited scope.Source named by the research packet.
Zdeněk Dvořák and Liana Yepremyan, “Independence number in triangle-free graphs avoiding a clique minor”. Proceedings of the American Mathematical Society 153(8) (2025), 3185-3195. DOI 10.1090/proc/16069. abstract and introduction. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Gives a current neighboring minor theorem and describes the unrestricted Hadwiger conjecture as unresolved.

An original CC0 restatement prepared by TheoremDB maintainers.

[#P23] Hadwiger's conjecture

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance