wu :: forums
« wu :: forums - Re: Polyhedron faces »

Welcome, Guest. Please Login or Register.
Nov 13th, 2024, 11:30pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, towr, Grimbal, william wu, Eigenray, SMQ)
   Re: Polyhedron faces
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Re: Polyhedron faces  (Read 948 times)
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Polyhedron faces  
« on: Mar 22nd, 2007, 12:42am »
Quote Quote Modify 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 22nd, 2007, 12:48am by Aryabhatta » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: Polyhedron faces  
« Reply #1 on: Mar 22nd, 2007, 1:39am »
Quote Quote Modify Modify

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.
IP Logged
anant
Newbie
*





   


Posts: 5
Re: Polyhedron faces  
« Reply #2 on: Mar 22nd, 2007, 10:34pm »
Quote Quote Modify 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
*





  shishir_iitb  


Gender: male
Posts: 19
Re: Polyhedron faces  
« Reply #3 on: Mar 23rd, 2007, 9:55am »
Quote Quote Modify Modify

on Mar 22nd, 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: male
Posts: 1001
Re: Polyhedron faces  
« Reply #4 on: Mar 23rd, 2007, 12:32pm »
Quote Quote Modify Modify

on Mar 23rd, 2007, 9:55am, 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
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Polyhedron faces  
« Reply #5 on: Mar 23rd, 2007, 12:43pm »
Quote Quote Modify Modify

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.
IP Logged
anant
Newbie
*





   


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

I love this forum
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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