Author 
Topic: Re: Polyhedron faces (Read 948 times) 

Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Polyhedron faces
« on: Mar 22^{nd}, 2007, 12:42am » 
Quote Modify

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.

« Last Edit: Mar 22^{nd}, 2007, 12:48am by Aryabhatta » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Polyhedron faces
« Reply #1 on: Mar 22^{nd}, 2007, 1:39am » 
Quote Modify

If there are N faces, each can have 3 to N1 neighbours. That is N3 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.


IP Logged 



anant
Newbie
Posts: 5


Re: Polyhedron faces
« Reply #2 on: Mar 22^{nd}, 2007, 10:34pm » 
Quote Modify

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


IP Logged 



shishir85
Newbie
Gender:
Posts: 19


Re: Polyhedron faces
« Reply #3 on: Mar 23^{rd}, 2007, 9:55am » 
Quote Modify

on Mar 22^{nd}, 2007, 10:34pm, 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?


IP Logged 



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Polyhedron faces
« Reply #4 on: Mar 23^{rd}, 2007, 12:32pm » 
Quote Modify

on Mar 23^{rd}, 2007, 9:55am, shishir85 wrote: Can you please explain this? 
 n nodes, possible degrees of each node between 0 and n1, the graph is connected, hence proved.  AI


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Polyhedron faces
« Reply #5 on: Mar 23^{rd}, 2007, 12:43pm » 
Quote Modify

In fact, graph need not be connected. n node, 0 to n1 degrees. Consider vertex with n1 degree > connected to the rest. Contradiction, hence duplicate degree.


IP Logged 



anant
Newbie
Posts: 5


Re: Polyhedron faces
« Reply #6 on: Mar 27^{th}, 2007, 11:42pm » 
Quote Modify

I love this forum


IP Logged 



