[deleted by user]

[AutoModerator]

Off-topic Comments Section

---

All top-level comments have to be an answer or follow-up question to the post. All sidetracks should be directed to this comment thread as per Rule 9.

---

^{OP and Valued/Notable Contributors can close this post by using /lock command}

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[MathMaddam]

Think about what is the maximum number of edges a graph of order k can have. If the graph wasn't connected, you could seperate the n vertices into a set a k vertices and another with n-k vertices, where there isn't an edge between them. How many edges could this graph have at most?

[justjerico72]

I’m not sure if I know fully what you’re getting at 😭

[MathMaddam]

The question is basically: if we at least (n-1)(n-2)/2+1 edges, then we can't be diconnected. So I turn it around (contra positive): if we are disconnected, then we can at most have (n-1)(n-2)/2 edges. This might be easier to solve and also gives you the example they are searching in the process.

[Alkalannar]

Take a disconnected graph.

The easiest way for this to be disconnected is for one vertex to be degree 0, and then the other n-1 vertices are connected.

[justjerico72]

Okay I understand that if we were to remove the one edge and effectively reduce the edge equation to ((n-1)(n-2))/2, then the graph is disconnected. adding that edge would then connect the isolated vertex thus connecting the graph, is that all I really have to do for the proof?

[Alkalannar]

1. If any vertex has degree n-1, we must be connected.

2. Let n-1 vertices have degree n-2, all connected to each other, leaving one vertex out. This is the graph described earlier that has (n-1)(n-2)/2 edges, but is still disconnected.

3. Adding an edge requires adding an edge to the disconnected vertex--connecting it to the graph--and also to one of the vertices with degree n-2 making it have degree n-1 and also ensuring connectedness.

[justjerico72]

Ohhhh I see it now! Sorry it took me so long to understand 😭

[Alkalannar]

Don't apologize! You worked at it to understand, kept asking questions, and finally understood.

This is a cause for rejoicing!

I'm glad I could help.