Skip to content

Erdős Problem #426

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

A graph can contain another graph as a subgraph in many different ways. Erdős Problem 426 studies the unusually restrictive situation in which a particular graph type occurs exactly once. The subgraphs in this problem need not be induced: extra edges of the larger graph may be omitted when selecting a copy of the smaller one.

For a graph \(G\) on \(n\) vertices, let \(U(G)\) count the different isomorphism types that occur exactly once as subgraphs of \(G\), and let \(M(n)\) be the largest possible \(U(G)\) among all graphs on \(n\) vertices. The problem asked whether this maximum could be a positive constant fraction of the approximate total number of nonisomorphic graphs on \(n\) vertices:

\[ \frac{2^{\binom n2}}{n!}. \]

This normalization arises because there are \(2^{\binom n2}\) labelled simple graphs, and almost all large graphs have no nontrivial automorphisms, so dividing by \(n!\) approximates the number of isomorphism classes. The question is whether one host graph can contain a constant proportion of these types uniquely, not merely contain them at all.

A small example

Take the triangle \(K_3\), the complete graph on three vertices. It contains a subgraph isomorphic to the single-edge graph \(K_2\) in three ways, one for each edge. Therefore \(K_2\) is not a unique subgraph type of \(K_3\). The triangle \(K_3\) itself occurs only once as a subgraph, namely using all its vertices and all three edges, so it is a unique type.

This example distinguishes a mathematical occurrence from an isomorphism type. There is one isomorphism type called \(K_2\), but the host has three copies. The number of types occurring once must not count the three copies as three unique types. Likewise, choosing only induced subgraphs changes the counting problem: a three-vertex path is not an induced subgraph of \(K_3\), but can be obtained as a noninduced spanning subgraph by omitting one edge.

These small statements can be checked by listing the three vertices and their possible edge subsets. They illustrate the definition but say nothing about the asymptotic count for large \(n\).

What is known

The problem originated with Erdős and Entringer, On the number of unique subgraphs of a graph (1972), and was discussed by Erdős in Problems and results in graph theory and combinatorial analysis, Proceedings of the Fifth British Combinatorial Conference (1976), pp. 169–192. Successive constructions by Entringer and Erdős, Harary and Schwenk, and Brouwer produced many unique subgraph types but did not reach a constant fraction of the full graph-isomorphism scale.

The final negative solution is Domagoj Bradač and Micha Christoph, Unique subgraphs are rare, first submitted in October 2024. They prove that

\[ M(n)=o\left(\frac{2^{\binom n2}}{n!}\right). \]

In words, even the best host graph on \(n\) vertices contains a proportion of uniquely occurring graph types that tends to zero. This answers the original question no. The maintained Erdős Problems #426 entry marks the result DISPROVED (LEAN) and reports a quantitative refinement of order \(\log\log\log n/\log\log n\) for the normalized maximum. Such a refinement changes the rate of decay, not the basic negative answer.

Erdős had offered USD 100 for a construction achieving the desired positive fraction and USD 25 for a disproof. This historical context is not a claim that GCL earned or administers an award. The published mathematical resolution is attributed to the named researchers and must remain separate from any GCL formal verification or editorial disposition.

GCL's current state

The original source-audit issue #1696 pins teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen entry records the statement as disproved with a reported Lean formal-solution status. The maintained problem page agrees with the negative mathematical conclusion.

The pinned FormalConjectures 426.lean has Git blob 5f389f8fc147652361ecd0290628a9c8ab0e1816. It defines unique subgraphs and expresses an infinitely-often positive-fraction version of the question with a negative answer. The pinned main theorem ends in by sorry, although it links an external Lean formalization and includes a proved elementary sanity check for the empty graph. The presence of an external formalization is not evidence that its precise commit, axioms and statement correspondence have been replayed by GCL in this session.

The original authenticated source return is issue #1696, RESULT/1 comment #6157292342. The V2 editorial ledger remains the sole authority for accepted article coverage.

What remains

The mathematical question is settled at the published-paper level. A bounded source review should match the proof's definition of \(M(n)\) to the pinned formal predicate and verify that an infinitely-often positive-fraction statement is negated exactly by the asserted little-o theorem. The presence or absence of the word induced must be checked at every interface.

A small independent fixture could enumerate all nonisomorphic subgraph occurrences of graphs on at most four vertices, first by direct edge-subset enumeration and then by a separate graph-isomorphism routine. The two counts must agree, including the \(K_3\) example. Such finite tests establish only an interface checksum; they do not replay Bradač and Christoph's asymptotic proof. Acceptance requires exact finite agreement and a theorem-to-formal-source concordance. Incorrect copy counting, conflating labelled embeddings with unique occurrences, or claiming Lean certification from a pinned placeholder is a falsification condition. Stop after these bounded checks, treating external formal replay as a separate governed task.

Sources and claim boundaries

Historical origin: Entringer and Erdős (1972) and Erdős (1976), cited in the pinned FormalConjectures file. Primary resolving source: Bradač and Christoph, arXiv:2410.16233. Maintained interpretation and status: Erdős Problem #426. Original GCL assignment: issue #1696, frozen catalogue, and authenticated source audit.

The \(K_3\) examples are independently verifiable finite arguments. The general negative result is an externally published theorem, not an original GCL discovery. No independent full Lean replay, mathematical certification, protected admission or award claim is made.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1696 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction