edited by
947 views
1 votes
1 votes

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:

  1. There is always a graph with all vertices connected to at least $42$ other vertices.
  2. For all such graphs the number of vertices connected to at least $42$ other vertices is at most cn for some constant $c < 1$.
  3. There are no graphs with each vertex connected to at most $38$ other vertices.
  4. None of the above
edited by

Please log in or register to answer this question.

Related questions

2 votes
2 votes
2 answers
2
go_editor asked May 19, 2016
615 views
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1...