wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> putnam exam (pure math) >> Re: Polyhedron faces
(Message started by: Aryabhatta on Mar 22nd, 2007, 12:42am)

Title: Re: Polyhedron faces
Post by Aryabhatta on Mar 22nd, 2007, 12:42am
Given a polyhedron, form a Graph G as follows:

For each face, add a vertex to G. If faces f and g share an edge in the polyhedron, add an edge in G between corresponding vertices.

The degrees of a vertex is same as the number of sides to the corresponding face.

It is easy to show that any connected graph with 2 or more vertices has two vertices of same degree.

Title: Re: Polyhedron faces
Post by Grimbal on Mar 22nd, 2007, 1:39am
If there are N faces, each can have 3 to N-1 neighbours.  That is N-3 values for N items.  The pigeonhole principle tells there are at least 3 collisions, for instance 4 of the same type, 3 pairs, or one triplet and one pair.

Title: Re: Polyhedron faces
Post by anant on Mar 22nd, 2007, 10:34pm
It is easy to show that any connected graph with 2 or more vertices has two vertices of same degree.

This again is from Pigeon Hole Principle

Title: Re: Polyhedron faces
Post by shishir85 on Mar 23rd, 2007, 9:55am

on 03/22/07 at 22:34:42, anant wrote:
It is easy to show that any connected graph with 2 or more vertices has two vertices of same degree.

This again is from Pigeon Hole Principle


Can you please explain this? Thanks.

Also, aryabhatta's solution seems to hold not only for convex polyhedra (as was originally asked) but for all kinds of polyhedra. Am I right?

Title: Re: Polyhedron faces
Post by TenaliRaman on Mar 23rd, 2007, 12:32pm

on 03/23/07 at 09:55:18, shishir85 wrote:
Can you please explain this?

n nodes, possible degrees of each node between 0 and n-1, the graph is connected, hence proved.

-- AI

Title: Re: Polyhedron faces
Post by Aryabhatta on Mar 23rd, 2007, 12:43pm
In fact, graph need not be connected.

n node, 0 to n-1 degrees. Consider vertex with n-1 degree -> connected to the rest. Contradiction, hence duplicate degree.

Title: Re: Polyhedron faces
Post by anant on Mar 27th, 2007, 11:42pm
I love this forum



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board