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. ^[1]

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.

Its operative boundary is not supplied by the name alone. Preserve this identity: The largest integer k such that the complete graph on k vertices occurs as a minor of a given undirected graph. Validity boundary: The complete graph must arise as a minor under the allowed operations and k must be maximal; clique size alone is insufficient. The entry therefore captures a reusable specialist role structure rather than a topic label, a single historical instance, or a loose analogy.

Structural Signature¶

Sig role-phrases:

the host graph — the graph whose minor structure is measured
the complete target — K_k for a candidate integer k
the minor operations — vertex deletion, edge deletion, and edge contraction
the branch sets — disjoint connected subgraphs representing target vertices
the pairwise adjacencies — edges witnessing every target pair
the maximum order — the greatest feasible k, reported as h(G)

Recognition test. A case qualifies only when the analyst can map the declared the host graph, the complete target, the minor operations, the branch sets, the pairwise adjacencies and preserve the specialist validity conditions. Shared vocabulary, a similar output, or a generic instance of one parent relation is insufficient.

What It Is Not¶

Not clique number. A minor clique may emerge after contractions even when no equal-size subgraph clique exists.
Not chromatic number. Hadwiger's conjecture relates the quantities but does not define them as equal.
Not treewidth. Treewidth bounds related structure but uses decompositions rather than the same maximum.
Not topological minor number. A topological minor requires internally vertex-disjoint path subdivisions.
Not a count of all graph minors. The invariant optimizes only complete-minor order.

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. If the case retains only the portable skeleton described below, it should be named through a parent abstraction rather than as Hadwiger number.

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.

These moves separate definition, derivation, measurement, and interpretation. A formal consequence does not by itself prove that an observed case instantiates the abstraction, while an observed resemblance does not relax the formal or institutional recognition conditions.

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.

Examples¶

Canonical: a tree¶

Any tree with an edge has a K_2 minor, but no K_3 minor because deletion and contraction preserve acyclicity. Its Hadwiger number is therefore 2. ^[1]

Mapped back: the host graph; the complete target; the minor operations; the maximum order.

Applied / In Practice: a contracted clique model¶

Five disjoint connected regions of a graph have an edge between every pair. Contracting each region to one vertex produces K_5, certifying h(G) at least 5 even if the original graph has no five-vertex clique. ^[2]

Mapped back: the branch sets; the pairwise adjacencies; the complete target; the certified lower bound \(h(G)\ge 5\), with no claim that a \(K_6\) minor has been excluded.

Structural Tensions¶

T1: Subgraph visibility vs minor structure. Contractions reveal adjacency hidden across connected regions. Diagnostic: Is the claimed clique literal or contracted?

T2: Certificate vs maximality. A model proves a lower bound, not the exact invariant. Diagnostic: How is K_{k+1} excluded?

T3: Clique minor vs coloring. The conjectured coloring bound is not a definition. Diagnostic: Is a theorem or conjecture being imported?

T4: Mathematical definition vs computation. The invariant is crisp while finding it can be hard. Diagnostic: Is the claim exact or algorithmic?

T5: Minor vs topological minor. Branch sets permit contractions more freely than subdivisions do. Diagnostic: Which containment relation is used?

T6: Domain autonomy vs prime reduction. Optimization and Aggregation omit the specialist objects, constraints, and validity tests named above. Diagnostic: Would retaining only the portable parent pattern still satisfy the recognition test?

Structural–Framed Character¶

The five-criterion aggregate is 0.15 (structural). The judgment is criterion-specific:

Vocabulary travels — low (0.25). The complete vocabulary remains tied to the typed roles in the Structural Signature.
Evaluative weight — low (0.00). Application carries the stated degree of normative or interpretive judgment beyond structural recognition.
Institutional origin — low (0.25). The abstraction depends to this degree on a scholarly, technical, legal, or social convention.
Human-practice bound — low (0.00). Recognition depends to this degree on organized practice, language, measurement, or institutional action.
Import versus recognize — low (0.25). Beyond its home habitat, use of the full name increasingly becomes analogy rather than literal recognition.

The portable skeleton is a maximum is taken over complete structures reachable through a specified information-preserving reduction relation. The named abstraction remains structural because that skeleton alone does not supply its specialist objects, constraints, or tests.

Structural Core vs. Domain Accent¶

Structural core: A maximum is taken over complete structures reachable through a specified information-preserving reduction relation.

Domain accent: Finite graphs, complete minors, edge contractions, connected branch sets, clique order, and hadwiger's conjecture.

Why it does not clear the prime bar: Optimization and aggregation travel; the graph-minor witness system and complete targets do not. Generalization therefore routes through parent abstractions; preserving the specialist name requires the full accent.

Optimization (prime:optimization). The invariant selects the largest feasible complete-minor order.
Aggregation (prime:aggregation). Connected vertex sets are collapsed into branch-set representatives.

These are prose placement proposals only. They create no dag_edges; endpoint, redundancy, and cycle checks are recorded separately in the bundle's placement memo.

Relationships to Other Abstractions¶

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

Hadwiger number → Compression → Abstraction

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Hadwiger number sits in a sparse region of the domain-specific corpus (64^th 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

Not to Be Confused With¶

Clique number. largest complete subgraph. Tell: May vertices be contracted?
Chromatic number. fewest colors in a proper coloring. Tell: Is coloring or a minor optimized?
Treewidth. minimum-width tree decomposition. Tell: Is the certificate a decomposition or branch sets?
Topological Hadwiger number. largest complete topological minor. Tell: Must target edges be internally disjoint paths?
Colin de Verdière invariant. a spectral graph parameter related to minors. Tell: Is the value defined by matrices or K_k minors?

References¶

[1] Reinhard Diestel, Graph Theory, 5^th ed., Springer, 2017. registry ↩a ↩b

[2] Daniel J. Harvey and David R. Wood, “Hadwiger Number of Graphs with Small Chordality”, SIAM Journal on Discrete Mathematics 29(3), 2015. registry ↩