DECIDABLE
Resolved up to a finite check.
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?
A conjecture of Murty and Plesnik (see
[CaHa79]) (although Füredi credits this conjecture to Murty and Simon, and further mentions that Erdős told him that the conjecture goes back to Ore in the 1960s). The complete bipartite graph shows that this would be best possible.
This is true (for sufficiently large $n$) and was proved by Füredi
[Fu92].
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Noga Alon
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #742, https://www.erdosproblems.com/742, accessed 2026-04-11
