Results 1 to 2 of 2

Math Help - Proof of n-cube

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    15

    Proof of n-cube

    Write down a proof that the n-cube cannot be realized as a planar graph for any n >=4.

    I know I want to use the inequality of kF<=2E
    and F=E-V+2 but I am not sure how to find the values.
    A 4 cube has 16 nodes, and k = 3, so there are 48 edges, and 16 vertices. So there is 34 faces for it to be planar. But 102 is not less than 96 so a 4 cube is not planar.

    Not so sure how to make this into a proof though. Any help would be much appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by smellatron View Post
    Write down a proof that the n-cube cannot be realized as a planar graph for any n >=4.

    I know I want to use the inequality of kF<=2E
    and F=E-V+2 but I am not sure how to find the values.
    A 4 cube has 16 nodes, and k = 3, so there are 48 edges, and 16 vertices. So there is 34 faces for it to be planar. But 102 is not less than 96 so a 4 cube is not planar.

    Not so sure how to make this into a proof though. Any help would be much appreciated.
    The 4-cube has 16 vertices and 32 edges (4 edges meet at each vertex, and each edge connects 2 vertices). If the graph is planar then Euler's formula v–e+f=2 tells you that there must be 18 faces. But each face of the cube has 4 edges, and each edge is shared between 2 faces, so 18 faces would need 36 edges—contradiction, so the graph is not planar.

    If n>4 then the graph of the n-cube contains the graph of the 4-cube as a subgraph. So the n-cube's graph must also be non-planar.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. cube
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: April 1st 2011, 08:43 AM
  2. Square and Cube Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 17th 2011, 06:40 AM
  3. Cube
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 17th 2010, 12:23 PM
  4. Cube Root times Cube Root
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: December 1st 2009, 07:03 AM
  5. The Hilbert cube homeomorphic to the cube?
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: June 12th 2009, 10:35 AM

Search Tags


/mathhelpforum @mathhelpforum