2
$\begingroup$

Can anyone help me for this problem:

Give an example of undirected graph $G=(V,E)$ where $|V|=|E|+1$, but $G$ is not a tree.

thanks

$\endgroup$

4 Answers 4

2
$\begingroup$

How about a triangle plus an isolated point?

Triangle plus an isolated point

$\endgroup$
2
  • $\begingroup$ please explain more not clear to me the answer $\endgroup$
    – leena adam
    Apr 22, 2013 at 11:25
  • 1
    $\begingroup$ @leenaadam, a triangle has three vertices and three edges, plus an isolated vertex there are 4 vertices and three edges in the graph. $\endgroup$
    – Easy
    Apr 22, 2013 at 11:26
2
$\begingroup$

As @Easy mentioned, you may take cycles $C_n$ and an isolated vertex.

$\endgroup$
1
  • $\begingroup$ CW? ${ }$ ${ }$ $\endgroup$
    – draks ...
    Sep 15, 2013 at 21:01
1
$\begingroup$

Hint: Try a disconnected graph.

$\endgroup$
1
$\begingroup$

For $n \geq 1$, since (a) all $n$-vertex trees have $n-1$ edges, (b) all connected graphs have spanning trees, and (c) disconnected graphs are not trees, we have the following:

Theorem: Let $G$ be a graph with $n \geq 1$ vertices and $n-1$ edges. Then $G$ is a tree if and only if $G$ is connected.

$\endgroup$

You must log in to answer this question.

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