Simple graph connectivity when minimum degree is $\geq \frac{n-1} {2}$

25 Views Asked by At

Essentially the title, but we had to prove that the simple graph is connected. I know the standard way of doing this by assuming two components and then contradiction. But i wanted to know about another approach that i used: Since we know that tree has $n-1$ edges and minimum edges in our case would be $\frac{n(n-1)}{4}$ and if I assume that our graph has more edges than a tree than we get $n\geq4$. Also by the formula of maximum edges in a graph with k components, $\frac{(n-k)(n-k+1)}{2}$ and comparing it with our graph for $k=2$, we get $n\leq4$. Now I know that trees are minimal connected and so this approach might not be entirely correct but I am unable to find any counter examples. So kindly help me with a counter example or simply help me to make this proof more rigorous or justifiable. Thank you!