Results 1 to 2 of 2

Thread: 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 $\displaystyle v_1,v_2,\ldots,v_{2^k}$. Let G' be a duplicate of G with the vertices labeled $\displaystyle v'_1,v'_2,\ldots,v'_{2^k}$. Add edges between $\displaystyle v_1$ and $\displaystyle v'_1$, $\displaystyle v_2$ and $\displaystyle v'_2$, $\displaystyle v_3$ and $\displaystyle 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 $\displaystyle 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
    $\displaystyle 2\cdot4+4=12$
    $\displaystyle 2\cdot12+8=32$
    $\displaystyle 2\cdot32+16=80$

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

    $\displaystyle 2 \cdot 2^{2-1}=4$
    $\displaystyle 3 \cdot 2^{3-1}=12$
    $\displaystyle 4 \cdot 2^{4-1}=32$
    $\displaystyle 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: Mar 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 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: Aug 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum