Skip to content

Hadwiger number

The largest integer k such that the complete graph on k vertices occurs as a minor of a given undirected graph.

Version
v2 · 2026-09-19 · History
Domain-specific #
1970
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Structural Graph Theory → Mathematics
Aliases
Hadwiger invariant

Core Idea

Hadwiger number is the largest integer k such that the complete graph on k vertices occurs as a minor of a given undirected graph.

The Hadwiger number h(G) of a finite graph G is the largest integer k for which the complete graph K_k occurs as a minor of G. Equivalently, G contains k pairwise disjoint connected branch sets with at least one edge joining every pair. It measures complete connectivity obtainable by deleting vertices or edges and contracting edges, not merely a clique already present.

How would you explain it like I'm…

Squish-and-Connect Count

Imagine dots joined by strings. You're allowed to erase dots or strings, and to squish two dots that share a string into one bigger blob. The Hadwiger number is the most blobs you can end up with where every blob has a string to every other blob.

Biggest Hidden All-Connected Group

A graph is a bunch of dots with lines between some of them. You can change it by deleting dots or lines, or by shrinking a line so its two ends merge into one dot. The Hadwiger number is the largest number k so that, after such changes, you get k dots that are all connected to each other. It's like grouping the dots into teams, where each team is connected inside itself, and every pair of teams has at least one line between them. This can be much bigger than the biggest group of dots that are already all joined to each other.

Largest Complete Graph Minor

In graph theory, a minor of a graph G is anything obtained by deleting vertices, deleting edges, and contracting edges (merging their endpoints). The Hadwiger number h(G) is the largest k such that the complete graph K_k—k vertices all mutually joined—is a minor of G. Equivalently, you can find k disjoint connected sets of vertices with at least one edge between every pair of sets. This differs from the clique number, which only counts complete subgraphs already sitting in G without contraction. A long cycle, for example, has no triangle but contracts down to one, so its Hadwiger number is 3 while its clique number is 2.

 

For a finite undirected graph G, the Hadwiger number h(G) is the largest integer k such that K_k is a minor of G. Minors arise from sequences of vertex deletions, edge deletions, and edge contractions. An equivalent formulation uses branch sets: G has a K_k minor iff there are k pairwise disjoint vertex subsets, each inducing a connected subgraph, with at least one edge between every pair of subsets. Contracting each branch set to a vertex then produces K_k. Because contraction can create adjacency that was not present, h(G) is always at least the clique number and can be much larger; for example, any cycle of length at least 3 has h = 3 though cycles longer than 3 contain no triangle. Establishing h(G) = k requires both exhibiting a K_k minor and showing that no K_{k+1} minor exists.

Scope of Application

The abstraction recurs literally within finite undirected graph theory and algorithms concerned with minors, coloring, and structural density. The following habitats preserve the same recognition machinery; they are not invitations to extend the name metaphorically.

  • Minor theory. complete minors summarize contractible connectivity.
  • Graph coloring. the invariant frames Hadwiger's conjecture.
  • Extremal graph theory. edge density and forbidden minors bound h(G).
  • Algorithm design. fixed-k tests search for branch-set models.
  • Network structure. robust interconnected regions can be compared through complete minors.

Clarity

State whether graphs are finite, simple, and undirected and exhibit either an operation sequence or a branch-set model. A visible clique supplies only a lower bound; proving the number also requires excluding K_{k+1} as a minor.

A practical identification audit begins with the typed roles rather than the title: establish the host graph, verify the complete target, then test the remaining conditions and exclusions.

Manages Complexity

The invariant compresses a large minor order into one extremal value. Its branch-set certificate supports constructive lower bounds, while upper bounds require global structural or algorithmic reasoning.

The compression remains accountable because each simplification has a named failure condition. Disagreement can be localized to a missing role, an invalid assumption, an ambiguous measurement, or a neighboring abstraction instead of being hidden inside an unanalyzed label.

Abstract Reasoning

R1. Fix a candidate k and the host graph convention. R2. Search for k disjoint connected branch sets. R3. Verify an edge between every pair of branch sets. R4. Contract each branch set to obtain a K_k minor certificate. R5. Prove maximality by excluding the next complete minor using a valid bound or exhaustive test.

Knowledge Transfer

The definition transfers literally among graph classes under the same minor relation. Optimization and aggregation are parents; social prominence or visual density is not a Hadwiger number.

The transfer boundary is explicit: DOMAIN-SPECIFIC PASS / PRIME FAIL: The invariant is computed across graphs through edge contractions and vertex or edge deletions. Literal recognition retains the specialist vocabulary and validity conditions of graph minor theory; outside that setting only broader parent operations transfer. The safe move beyond the home habitat is to carry the applicable parent relation and leave the specialist name behind unless every defining role remains literal.

Relationships to Other Abstractions

Local relationship map for Hadwiger numberParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Hadwiger numberDOMAINPrime abstraction: Compression — presupposesCompressionPRIME

Current abstraction Hadwiger number Domain-specific

Parents (1) — outgoing typed relations

  • Hadwiger number presupposes Compression Prime

    The accepted reference-grade review places Hadwiger number under Compression because the child instantiates or depends on the parent's broader structure while retaining its own constitutive identity.

Hierarchy paths (3) — routes to 3 parentless roots

Neighborhood in Abstraction Space

Hadwiger number sits in a moderately populated region (40th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Structures & Combinatorial Objects (46 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25