Results 1 to 2 of 2

Math Help - Graph theory

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Graph theory

    How do I show that the k-cube has 2^k vertices and k2^k-1 edges?

    Any advice? Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    wil
    wil is offline
    Junior Member wil's Avatar
    Joined
    Apr 2005
    From
    Portland, OR
    Posts
    25

    k-cube vertices and edges (rough explanation)

    Quote Originally Posted by jzellt View Post
    How do I show that the k-cube has 2^k vertices and k2^k-1 edges?
    I'm taking my first Graph Theory course now as a undergrad. I may not be the best person to answer this question. However, it's been sitting in the Urgent Homework Help forum for over 24 hours. Even if I can't give a complete solution, maybe I can put you on the right path.

    Consider the process of constructing a (k+1)-cube from a k-cube. Suppose the vertices of a k-cube G are labeled v_1,v_2,\ldots,v_{2^k}. Let G' be a duplicate of G with the vertices labeled v'_1,v'_2,\ldots,v'_{2^k}. Add edges between v_1 and v'_1, v_2 and v'_2, v_3 and v'_3 and so on. The resulting graph is a (k+1)-cube.

    The vertices have doubled in going from k to k+1, so the 2^k should be provable with induction.

    Since I didn't know how many edges the k-cube had, it took a little while for me to tease out that "k2^k-1" meant k \cdot 2^{k-1}. Try using the MATH tags next time or putting the exponent in parentheses. Anyway...

    Again, I think induction is the way to go. Edgewise, when you go from the k-cube to the (k+1)-cube, you double the number of edges in the k-cube, then add a number of edges equal to the number of vertices in the k-cube. The first few terms of this sequence (starting with the 2-cube aka square):
    4
    2\cdot4+4=12
    2\cdot12+8=32
    2\cdot32+16=80

    Starting with k=2, the first few terms of the k \cdot 2^{k-1} sequence are:

    2 \cdot 2^{2-1}=4
    3 \cdot 2^{3-1}=12
    4 \cdot 2^{4-1}=32
    5 \cdot 2^{5-1}=80

    Yikes. My sketchy explanation turned out sketchier than I'd thought, but I hope it helps get you started towards a proof.

    Wil
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum