In a group of n friends (n >= 2), atleast 2 of them will have same no: of

friends.

Reformulating as a graph theory problem

In an undirected graph G (with no self-loops) with n = |V| >= 2, atleast 2

vertices will have same degree.

Proof. We use proof by cases

(case 1). G is connected

The degree of a vertex can be any of n-1 different values 1, 2,...,n-1(A

vertex with degree 0 will imply that G is not connected). There are n

vertices in the graph. So atleast 2 of them should have same degree by

pigeonhole principle.

(case 2). G is not connected

The degree of a vertex can be any of n-1 different values 0,1,...,n-2 (A

vertex with degree n-1 will imply that G is connected). A similar argument

as case 1 applies.

## Thursday, October 2, 2008

Subscribe to:
Post Comments (Atom)

## 8 comments:

Are you into some new book?

Vivek.

vivek is showing interest in theoretical mathematics.. u guys can have real fun :)

Anish Bhaskaran

@vivek

Nop, Our plain old CLRS has all these problems

@ani

We're having fun

:-)

Enjoy guys... i am not at all jealous :)

btw.. whats this plain old CLRS? Just outta curiosity :)

Anish Bhaskaran

Introduction to Algorithms, Cormen et. al.Theoretical mnathematics (shudn't we say it as theorotical computer science?) and me !!!! Ahem Ahem.. not my cup of coffee, buddies...

Vivek.

@balu,

Ohh nammude swantham Intro to algo.. Great.. Thanks..

@Vivek,

Elima mathi mashe.. u are an future gcc developer and that too in optimization algorithms.. isnt that we call theoretical comp/maths???

@both,

why dont u guys include sandy too.. nalla rasam ayirikkum :)

~Anish

@Anish

I really didn't get u !!!

Post a Comment