ACE Testseries

Question

In a connected simple graph with 30 edges the maximum number of vertices possible are

Answer 1

As the graph is a simple connected graph , for a simple connected graph with n vertices minimum no of edges is n-1.

So n-1=30 implies n=31

Answer 2

A graph with n vertices has $\frac{n\left ( n-1 \right )}{2}$ edges

$\therefore \frac{n(n-1)}{2} = 30$

n(n-1) = 60

n2-n=60

n2-n-60=0

Applying Sridharacharya formula, we get n = 8 (approx)

Eliminating one of the roots as vertices cannot be negative.

Comments

n won't be 60

It will be approx 8 in this case

---

is it compulsory ????

u r saying complete graoph i think complete graph will minimise the no of vertices...

and n(n-1) =60 then n=60 how??

---

Check now

---

If it is a tree then the number of vertices will be 31

Am I correct?

---

https://math.stackexchange.com/questions/1570642/graph-theory-show-maximum-number-of-edges-in-a-simple-graph

---

@Vipin Rai yup vertices =31

---

@Gupta731 it is the case for minimum number of vertices and maximum number of edges