0
$\begingroup$

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$
1
  • $\begingroup$ "For every two vertices that are not connected through an edge, is their degree at least n-1" what do you mean? $\endgroup$ – Average-user Jun 4 at 13:10
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.