CMI2010-A-06

Question

A simple graph is one with no self-loops or multiple edges. Among the simple graphs with $n$ vertices and at most $20n − 3$ edges:

• A. There is always a graph with all vertices connected to at least $42$ other vertices.
• B. For all such graphs the number of vertices connected to at least $42$ other vertices is at most cn for some constant $c < 1$.
• C. There are no graphs with each vertex connected to at most $38$ other vertices.
• D. None of the above

Comments

is answer  is option  A ?

---

Option B should be the correct answer.