1
$\begingroup$

Let $G=(V,E)$ be an undirected graph.

Prove or disprove: If $|E|\le |V| - 1$ then $G$ is acyclic.

I am unsure about if this is even true or not in the first place. I know that trees have $n-1$ edges, but I do not know if this quality can deem that $G$ is acyclic (a tree).

$\endgroup$
1
$\begingroup$

Take a triangle and add an isolated vertex, you have a graph with $|E|\leq |V|-1$ and a cycle.

If you add the hypothesis $G$ is connected however, then it is true.

$\endgroup$
1
$\begingroup$

HINT: Trees are simply the connected acyclic undirected graphs. Thus, every component of an acyclic undirected graph is a tree. (Indeed, another name for acyclic undirected graphs is forest.) Now use what you know about trees to prove a formula relating the number of vertices of a forest to the number of edges and the number of components (trees).

$\endgroup$
11
  • $\begingroup$ Doesn't the fact that it is not specified that $G$ must be connected as @Gamamal stated below make this not true for ANY undirected graph $G$ though? $\endgroup$ – Groups n' Stuff Apr 29 '15 at 4:10
  • $\begingroup$ @Groupsn'Stuff: What I wrote is true as written, but it was probably too obscure a hint. Were you to pursue it to the end, you’d find that Gamamal’s graph does not satisfy the formula in question, and conversely, the formula would make it very easy to come up with counterexamples like that one. Since you have Gamamal’s answer available, I’ll delete this one; let me know when you’ve seen this comment. $\endgroup$ – Brian M. Scott Apr 29 '15 at 4:12
  • $\begingroup$ So as the statement stands, @Gamamal is correct because the condition of being connected is not present, but if it were I would see that this statement is true? $\endgroup$ – Groups n' Stuff Apr 29 '15 at 4:15
  • $\begingroup$ Why do you say my graph does not satisfy the formula? $3\leq 4-1$ $\endgroup$ – Yorch Apr 29 '15 at 4:17
  • $\begingroup$ @Gamamal: I did not say that. I said that it does not satisfy the formula that my answer was designed to help the OP discover, the one relating the numbers of vertices, edges, and trees of a forest. $\endgroup$ – Brian M. Scott Apr 29 '15 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.