253 views
0 votes
0 votes
Every graph with fewer edge than vertices has component of tree(explain)

1 Answer

1 votes
1 votes
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.

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
2
Hrithik Vashishtha asked Jan 24, 2023
361 views
p ->(q->r). Could you please tell me how it is a tautology?
1 votes
1 votes
1 answer
3
0 votes
0 votes
1 answer
4
Sagar475 asked Jan 15, 2022
286 views
If 2,-4 are the eigen value of a non-singular matrix A and IAI=-8, then the eigen vaule of Adj A are x and -y then the value x+y is ?