retagged by
625 views
1 votes
1 votes

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

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

2 Answers

2 votes
2 votes
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.

Related questions

6 votes
6 votes
3 answers
3
gatecse asked Sep 13, 2019
752 views
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ ...
1 votes
1 votes
2 answers
4