Test by Bikram | Mathematics | Test 2 | Question: 2

Question

The total number of vertices in a graph is $n = 6$.

The maximum number of possible edges (so that the graph remains disconnected) is ______.

Answer 1

the maximum no of possible edges  such that the graph remains disconnected is -

Take a complete graph with n-1 vertices and let the n'th vertex be isolated.

Thus total edges = (n-1)C2 (complete graph) + 0 (isolated vertex) = (n-1)(n-2)/2 = 5*4/2 = 10

Answer 2

(n-1)(n-2)/2
now put n = 6 , it becomes (5 * 4)/2 = 10

Comments

see if there are 5 edges, there is a possibility the graph becomes connected.

Now, we can do complete graph with 5 vertices, so that one vertices become disconnected. Is it taking like that?

---

 The maximum number of edges in a graph (connected or  disconnected) is (n )*(n-1) /2 = nC₂ .

This is because instead of counting edges, you can count all the possible pairs of vertices that could be its endpoints. That's the same as the maximum number of [unique] handshakes among n people.

If a graph is not connected, it has at least two connected components. If you want the maximum number of edges, you want to consider exactly two connected components.

Suppose we have 1 vertex on one side and other (n-1) vertices on another side.To make it connected maximum possible edges(if consider it as complete graph) require is (n-1)C₂ which is (n-1)(n-2)/2 .

So to make it disconnected , we have 1 separate vertex on another side which is not connected.Thus the maximum possible edges is (n-1)C₂

Answer 3

For n = 6, maximum number of edges possible = $6(5)/2 = 15$.

This will be a complete graph of 6 vertices. Each vertex will have the degree 5. (because complete)

To disconnect keeping maximum edges, just isolate a single vertex. => Remove 5 outgoing edges from a vertex.

 

So, $15-5=10$