5
$\begingroup$

enter image description here

(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.

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$ Commented Jan 7, 2018 at 17:25
  • $\begingroup$ Can these graphs be multigraph? $\endgroup$
    – ArsenBerk
    Commented Jan 7, 2018 at 17:31

2 Answers 2

2
$\begingroup$

Pick a subgraph of the (e) graph which is a tree. It has 4 edges. Then add missing 8 edges one-by-one. Every time you add an edge, it connects vertices which are already connected, so at least one simple cycle is added; so there are no less than 8 simple cycles in that graph.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The proposition I said can be proved by induction. $\endgroup$
    – Numbermind
    Commented Jan 9, 2018 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .