made easy test series

Question

Every graph with fewer edge than vertices has component of tree(explain)

Answer 1

Let's say there are $k$ components of a graph G=(V,E) where |V| = n and |E|=n-1. (At-most edges).

Now, if the number of vertices in each component is represented as $k_i$, then

$\sum_{i=1}^{k}k_i=n$

For a cycle to exist in a graph of $a$ edges, there should be atleast $a$ edges.

Thus, for cycle to exist in every component, each component with vertices $k_i$ must have atleast $k_i$ edges.

Thus, even sum of all edges must be atleast $n$ for cycle to exist in every component of the graph. But we have $n-1$ edges only.

Thus, there will always be atleast 1 component with no cycles in it. A graph with no cycles in it is a tree.