|
||
|
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:
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:
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 |