ISI2017-PCB-CS-1(b)

Question

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$.

Comments

What it means to partition a graph?? removing any edges??

---

I think so, then only graph can be converted into trees

---

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

---

https://math.stackexchange.com/questions/2823289/graph-theory-degree-of-vertices-of-graph-when-it-can-be-partitioned-into-two-tr

Answer 1

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.