Problem 426

We say $H$ is a unique subgraph of $G$ if there is exactly one way to find $H$ as a subgraph (not necessarily induced) of $G$ . Is there a graph on $n$ vertices with

\gg \frac{2^{\binom{n}{2}}}{n!}

many distinct unique subgraphs?

Source: erdosproblems.com/426

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN), the site's label (site export of 2026-09-04): solved in the negative with a Lean-verified proof; on 2026-10-07 the public page's markup showed no label text. The community database (teorth/erdosproblems, data/problems.yaml as of 2026-09-28) corroborates the label, recording status "disproved (Lean)", which its commit of 20 April 2026 set, with formal_status Lean. The site's commentary credits Bradač and Christoph [BrCh24], whose Theorem 1.2 gives $f(n)=o(2^{\binom n2}/n!)$ for the maximum number $f(n)$ of unique subgraphs of a graph on $n$ vertices. The claim page (Bradač and Christoph, 2024) records the result, the site's acceptance and the public Lean formalization; the paper appeared in Proc. Amer. Math. Soc. 153 (2025), 4585-4593, doi:10.1090/proc/17303.

Br75: Brouwer, A. E., Note: "On the number of unique subgraphs of a graph" (J. Combinatorial Theory Ser. B 13 (1972), 112-115) by R. C. Entringer and P. Erdős. J. Combinatorial Theory Ser. B 18 (1975), 184-185.
BrCh24: Bradač, D. and Christoph, M., Unique subgraphs are rare. arXiv:2410.16233 (2024); Proc. Amer. Math. Soc. 153 (2025), 4585-4593, doi:10.1090/proc/17303.
EnEr72: Entringer, R. C. and Erdős, Paul, On the number of unique subgraphs of a graph. J. Combinatorial Theory Ser. B (1972), 112-115.
Er76b: Erdős, P., Problems and results in graph theory and combinatorial analysis. Proc. Fifth British Combinatorial Conference (1976), 169-192.
HaSc73: Harary, Frank and Schwenk, Allen J., On the number of unique subgraphs. J. Combinatorial Theory Ser. B (1973), 156-160.

Problem 426

Status

Proof claims

Discussion