Author |
Topic: Re: Polyhedron faces (Read 941 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Re: Polyhedron faces
« on: Mar 22nd, 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 22nd, 2007, 12:48am by Aryabhatta » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Polyhedron faces
« Reply #1 on: Mar 22nd, 2007, 1:39am » |
Quote 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 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 23rd, 2007, 9:55am » |
Quote 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:
Posts: 1001
|
|
Re: Polyhedron faces
« Reply #4 on: Mar 23rd, 2007, 12:32pm » |
Quote 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:
Posts: 1321
|
|
Re: Polyhedron faces
« Reply #5 on: Mar 23rd, 2007, 12:43pm » |
Quote 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 Modify
|
I love this forum
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print