# Graph theory and trees questions

(a) Is false.

If $G$ is a tree then: $|E|=|V|-1$

So, $|E|=9-1=8$. But because the sum of the degrees of all vertices is equal to $2|E|$, we have $2|8|=16\neq18$

(b) Is true

If $G$ is a graph then: $|E| \geq |V|-|W|$, where |W| is the number of connected parts of the graph. We have $|E| \geq |V|-|W|$, so $|7| \geq 12-5=7$

(c) Is false.

$|E| \geq |V|-|W|$

So $24 \geq 30-5=25$ and this is false

How do I prove that (d),(e) are false?

EDIT:

(d) Is false

If the graph is acyclic then it's a forest and we have $|E|=|V|-1$, so we should have $9=9-1=8$ which is impossible.

• If the graph in (d) is acyclic, doesn't it have to be a tree or a forest? That should allow you to apply the formula you used in (a). Commented Jan 7, 2018 at 17:25
• Can these graphs be multigraph? Commented Jan 7, 2018 at 17:31

I found out that if a graph $G$ is connected and $|E|=|V|+k$ then $G$ has atleast $k+1$ cycles.
In case of (e) we have $12=5+k \Leftrightarrow k=7$.
So $G$ has atleast $8$ cycles.
Conclusion: (e) is false because it says that $G$ has less than $8$ cycles.