Logo
All Random Solved Random Open
OPEN
Let $n\geq 3$ and $G$ be a graph with $\geq 2n+1$ vertices and $\binom{2n+1}{2}-\binom{n}{2}-1$ edges. Must $G$ be the union of a bipartite graph and a graph with maximum degree less than $n$?
Faudree proved that this is true if $G$ has $2n+1$ vertices.

See also the entry in the graphs problem collection.