CODEWITHSUNDEEP
graph-algorithm
Saurabh
Saurabh

Reputation: 156

Graph Algorithms

Let G be a graph having n vertices, none of which are isolated, and n−1 edges, where n ≥ 2. Show that G contains at least two vertices of degree 1.

I have tried this problem by using the property summation degree = 2|E| . Can this problem be solved by using pigeon hole principle?

Upvotes: 1

Views: 137

Answers (1)

Helen
Helen

Reputation: 811

I can't think of a sensible way of using the pigeon hole principle to solve this, I would do it like this:

Sum of degree = 2n - 2 = 2|E|

As no vertices may be isolated, all must have degree of at least 1, so there are n - 2 'spare' edge ends to attach. n-2 things to fit into n places mean at least 2 must be left empty (this is similar to the pigeon hole principle, but kind of opposite) so at least 2 vertices must have degree 1.

I think you'd be better off asking this kind of question here: https://math.stackexchange.com/

Upvotes: 1

Related Questions