Graph Theory theorem help

[violet cove]

Hello, I am studying graph theory, so I am trying to understand this particular theorem although I struggle with the "why this works" part of it

[formal coral]

Since the minimum degree is $\frac{1}{2}(p-1)$, any vertex has at least that amount of edges.

Now if the graph was disconnected, there would have to be two vertices that are not connected, in the sense that they are part of two disjoint parts of the graph (connected components).

Both of these vertices must be connected to at least $\frac{1}{2}(p-1)$ other vertices. However, remember they are in separate connected components, so there is no “double counting” in a sense. That means that each component must have at least $\frac{1}{2}(p+1)$ vertices.

[fluid dagger]

Azyrashacorki

[violet cove]

so we're applying the connected graph conditions to connected components of a disconnected graph, and adding them up together (since they're part of the same graph G), it isn't consistent with p+1 so by proof of contradiction it's right?

[formal coral]

Yes, essentially.
We assume it’s not connected, which means it has at least two distinct connected components

Then show both of them total too many vertices

[violet cove]

that makes a lot of sense

thanks man

.close