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
v1 · 2026-08-30 · History
Domain-specific #
1970
Origin domain
mathematics
Subdomain
structural graph theory
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.

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) — more general patterns this builds on

  • 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 sparse region of the domain-specific corpus (64th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Discrete Structures & Graph Algorithms (17 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08