Skip to main content
Source Link
D. Ror.
  • 399
  • 2
  • 18

Clinton Conley, Jul 13 '11 at 22:19 answered:

A finite forest has strictly fewer edges than vertices. And a finite graph with no acyclic connected component has at least as many edges as vertices.

j.c., Jul 14 '11 at 5:12 clarified:

The existence of a forest on your sets of vertices with $n$ edges implies that $k+l>n$. But there exist no graphs with $k+l$ vertices all of whose connected components contain cycles (i.e. have no components that are trees), as all such graphs must have at least $k+l$ edges, which was strictly greater than $n$.

Post Made Community Wiki by D. Ror.