Erdős problem 426 · problems.science

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?

Sources

Browse retained paths and inspect the exact material available for this Problem.

2 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

426.lean

Retained formal statement2 of 2

Sanity check: the empty graph ⊥ is a unique subgraph of itself. Its only subgraph is ⊥ (everything ≤ ⊥ equals ⊥), which is isomorphic to ⊥ via the identity.

FormalConjectures/ErdosProblems/426.leanErdos426.isUniqueSubgraph_bot_bot1 lineExact file

1∀ {V : Type u_1}, ⊥.IsUniqueSubgraph ⊥

TestStatement only, no proof

Sources

Search problems.science