Thursday, October 2, 2008

Friendship and the power of pigenhole principle

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.

8 comments:

Anonymous said...

Are you into some new book?

Vivek.

Anonymous said...

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

Anish Bhaskaran

Balagopal said...

@vivek
Nop, Our plain old CLRS has all these problems
@ani
We're having fun
:-)

Anonymous said...

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

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

Anish Bhaskaran

Balagopal said...

Introduction to Algorithms, Cormen et. al.

Anonymous said...

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

Vivek.

Anonymous said...

@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

sandeep-rb said...

@Anish
I really didn't get u !!!