Show that following Graph is connected
Let $G$ be a simple graph with $n$ Vertices. For every two vertices that are not connected through an edge, is their degree at least n-1. Show that G is connected.
I tried to do it indirectly by contraposition. Assuming that it is not connected and for every two vertices that are not connected through an edge their degree at least n-1, but I can't come further.
Moreover we have a formula that the sum of the degrees of vertices is equal to two times the number of edges, which means that the number of edges in our case has to be greater or equal to $\frac{n-1}{2}$ but also here I don't know how to expand it further.
For the connectedness until now we have mostly used the definition that every two vertices are connected through a path.
Thanks in advance for the help
$\endgroup$ 11 Answer
$\begingroup$Take vertices $a$ and $b$ not connected by an edge. Then, if I understand correctly $d(a) + d(b) = n-1$.
Call $A$ the set of vertices adjacent to $a$, and $B$ the ones adjacent to $b$. We clearly have $|A \cup B| \leq n-2$, which, since $|A \cup B| = |A| + |B| - |A \cap B|$ and $|A| + |B| = n-1$ implies $|A \cap B| \geq 1$. Then there must exist vertex $c$ which is adjacent to $a$ and to $b$ and therefore there is a path between $a$ and $b$.
$\endgroup$
