Graph Theory: Connected graph and vertex degrees

Question

- Background Information:

I am studying graph theory in discrete mathematics. I have come across this question with the provided solution from my professor, but I cannot understand part of the solution. I appreciate any clarification, thanks.

---

- Question and Solution:

---

- My questions:

Could you please explain...

1. the part that says "Thus each component will have at-least 1 + 1/2(n-1) vertices". Where is + 1 (the front one) coming from in the equation 1 + 1/2(n-1)?

2. why do we have only two of (1+1/2(n-1)) in the equation (1+1/2(n-1)) + (1+1/2(n-1)) =
   (n-1)+2 = n+1 ? What do those two (1+1/2(n-1)) + (1+1/2(n-1)) represent?

---

- My thinking:

1. Assuming n = 3, then deg(v) >= 1/2( 3 - 1) , so weget deg(v) >= 1, that means that each vertex of graph G has atleast degree of 1. This indicates that there can be more vertices that the vertex can be connected to, so that is why we use 1 + 1/2(n - 1).

2. Having two (1+1/2(n-1)) + (1+1/2(n-1)) is probably for the number of components that we have. I am not sure, maybe my professor is assuming the graph to have two components when it is disconnected during the process of proof by contradiction.

Answer 1

I'm addressing the points you listed under My Thinking.

1. We know that every vertex has degree $\ge (n-1)/2.$ So a vertex $v$ has at least that many neighbors, and they're all in the same component as $v$. But $v$ is also in that component, which makes $(n+1)/2$ vertices at least. (That is, the 1+ you asked about comes from $v.$)

2. Your professor is indeed assuming that the graph has more than one component. To say that a graph is connected is the same as saying that it has exactly one component, so the contradiction is that it has at least two components.

Answer 2

It seems to be simpler to prove directly that $G$ is connected: Let $v,u$ be two arbitrary vertices; we need to prove there is a part between them.

If $v$ and $u$ are joined by an edge, then we're done.

Otherwise: Together $v$ and $u$ are incident to at least $2\frac{n-1}2 = n-1$ edges, each of which goes to one of the $n-2$ other vertices in the graph. By the pigeonhole principle at least one of the other nodes must be hit by two of those edges. Since the graph doesn't have multiples edges, those two edges must connect it to both $v$ and $u$. So there's a path of length $2$ between them.