Redirected
in Graph Theory
842 views
1 vote
1 vote
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
in Graph Theory
842 views

4 Comments

What it means to partition a graph?? removing any edges??
0
0
I think so, then only graph can be converted into trees
0
0

@akash.dinkar12 how to proof this type of question?

0
0

1 Answer

0 votes
0 votes
Note that in a tree with n vertices the number of edges is (n-1).

Let us assume that the degree of all the vertices be greater than or equal to 4.

Now, assume that the graph G is partitioned into two trees T1 and T2.

Then T1 and T2 both can have at most n vertices.

So, T1 and T2 both can have at most (n-1) edges.

Since the graph G is partitioned into T1 and T2 we get that the graph G can have at most (n-1) + (n-1)= 2n – 2 edges. …………..(1)

Now, we have assumed that the degree of the vertices of G is greater than or equal to 4.

So, the sum of the degrees is greater than or equal to 4n.

Hence by hand-shaking lemma we get the number of edges is greater than or equal to (4n / 2) = 2n ……………….(2)

So, we get that the statements (1) and (2) are contradictory in nature.

Hence, our assumption is wrong.

Hence, there exist at least one vertex with degree less than 4.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true