Thread: Graph Theory
View Single Post
  #2  
Old November 19th, 2008, 11:12 AM
Plato Plato is offline
MHF Contributor

  
Join Date: Aug 2006
Posts: 6,718
Thanks: 69
Thanked 2,486 Times in 2,280 Posts
Plato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond reputePlato has a reputation beyond repute
Default
Here is a theorem relating the number of edges to the number of vertices in a planar graph: V \geqslant 3 \Rightarrow \quad E \leqslant 3V - 6.
In K_8 there are 28 edges. If you partition that graph into two subgraph you get \left\{ {E_1 ,V_1 } \right\}\,\& \,\left\{ {E_2 ,V_2 } \right\} where \left\{ \begin{gathered} E_1 + E_2 = 28 \hfill \\ V_1 + V_2 = 8 \hfill \\ \end{gathered} \right..
Now try for a contradiction.
Reply With Quote
The following users thank Plato for this useful post:
Donate to MHF