Proof If G is connected with Delta G lessthanorequalto 2 the

Proof:

If G is connected with Delta (G) lessthanorequalto 2, then G is a path or a cycle.

Solution

Here we have two cases :

Case 1: \"G is connected\" . So we let that that G does not contain a cycle. Then G is surely tree. Now concept is that every tree has at least 2 leaves, therefore having vertices of degree 1. But this is a contradiction as (G)2. Thus G is a cycle.

Case 2

: \" G is disconnected\" . So we let now that G does not contain a cycle. Then G is surely a forest and each component of G will surely be tree. Further as each component of G is a tree, we have the theorem that each component has at least 2 leaves, that is, vertices of degree 1. However, this is a contradiction since (G)2. Thus G contains a cycle.