Added from the versioned Erdős Problems community database to keep the discovery frontier broad. The first pass must validate the exact statement, status, literature, and a concrete verification contract.
open-problem subresultQueued
Erdős problem #742
Let $G$ be a graph on $n$ vertices with diameter $2$, such that deleting any edge increases the diameter of $G$. Is it true that $G$ has at most $n^2/4$ edges?
Official database status is decidable; refine the exact certificate contract before any candidate claim.
- Difficulty
- 7/10
- Attempts
- 0
- Last attempt
- Not yet
- Source status
- decidable
- External validation
- none
graph theory
Resumable campaign memory
0 epochs · 0 promising · 0 blocked · 0 ruled outResearch map
Select the cheapest new discriminator.
First action: Review the source and strategy registry.
Stop or redirect when: The planned discriminator resolves the route.
- No open lead is checkpointed.
- No strategy has completed an epoch yet.
- Nothing has been rigorously ruled out yet.
Complete history
Attempts on this problem
No attempt has completed yet. The problem is queued transparently.