maximum number of edges in a graph with components

Question

A graph G have 9 vertices and two components. What is the maximum number of edges possible in this graph?

Answer 1

A simple graph with n vertices and k components has at most (n-k)*(n-k+1)/2 edges. So the given graph can have at most (9-2)*(9-2+1)/2=28 edges under the assumption that it is a simple graph.

Comments

if they ask that " atleast how many edges are there in multigraph"

then our ans will be n-k ie 7 edges.??

---

Yes you are correct. @kunal

---

How you got this formula ? Can you explain ?

Answer 2

max edge possible when a graph is complete , and there is 2 component

so by splitting it 1 vertex in one component  and in other 8 vertices in other component we can have max edges .

in 8 vertices component it must be complete so it can have max edge ,

so max edge 8C2 = 28 edges

Comments

Not sure what you are doing here.But we can have max 28 edges here !

---

now see edited :)

---

Cool !

Answer 3

The maximum no of edges possible in a graph is n*(n-1)/2

 

consider 8 and 1 then it is 28

Answer 4

k=e-v+2

or, e=k+v-2

or,e=2+9-2

or,e=9

Comments

This question do not need  Eulers formula. This is easy combinatorical question.

See the answer by @anurag. Meanwhile whatever answer you have given is incorrect. We can have 28 edges.