Maximum number of vertices in a simple graph

Question

In a connected simple graph $G$ with $30$ edges, what is the maximum number of vertices possible?

According to me, the answer is 31, obtained in a star structured graph. But the solution manual claims that the answer should be $9$ .

Am I correct or what am I doing wrong? Please let me know.

Thanks in advance!

Answer 1

Idea:

You can ask what is a minimum number of vertices that graph is not connected and with 30 edges.

Then exsist partition $(A,B)$ with no edges between them. So we have $${|A|\choose 2}+{|B|\choose 2} \geq 30$$

where $n=|A|+|B|$ the number you are looking for.

---

Let $x=|A|$ then $|B|=n-x$ and $0<x<n$. So $$30\leq {x^2 +(n-x)^2-n\over 2}\leq {n-1\choose 2}+{1\choose 2}$$ and thus $$30\leq {n-1\choose 2}\implies n_{\min}= 9$$

Answer 2

Is the question asking instead for the minimum number of vertices for a simple graph with 30 edges? A simple graph of $n$ vertices has at most $\frac{n(n-1)}{2}$ undirected edges...that gives 36 edges for $n=9$, but only 28 edges for $n=8$.

Answer 3

There's a theorem in a book in my native language (not English), saying:

Suppose $G$ is a connected graph, with $p$ being the order and $q$ being the size, then: $$ p - 1 \leq q $$

Therefore: $$ p \leq q+1 $$ $$ p \leq 30+1 $$

Hence, $31$ should be the correct answer.