CMI2018-B-3

Question

Let $G$ be a simple graph on $n$ vertices.

• A. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.
• B. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.

Comments

https://gateoverflow.in/237427/graph-theory

Answer 1

Part (a)

Let's assume the graph has $n$ vertices.

We take $n-1$ vertices and form a complete graph with it .

So the situation can be imagined as only one vertex is not touched by any edge and other $n-1$ vertices are connected in the best possible way .

If we add one more edge , this edge cannot be within the chosen $n-1$ vertices otherwise the graph won't be simple anymore , and adding an edge to the isolated vertex will connect it.

Thus we get a connected connected graph here.

 

Part (b)

We take $n=3$

A-B C and we get a disconnected graph here.

Answer 2