Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: Graph Theory Prove Problem (Please help)

  1. #1
    Newbie
    Joined
    May 2018
    From
    greece
    Posts
    4

    Graph Theory Prove Problem (Please help)

    Show that a cube Qn includes a number ofQk cubes.
    (We know that k<=n.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    Re: Graph Theory Prove Problem (Please help)

    Please define a cube Qn or Qk. Is that the number of dimensions of the cube? I am picturing vertices corresponding to n-tuples where each coordinate is in $\{0,1\}$ and edges between vertices if and only if the vertices differ by exactly one coordinate.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2018
    From
    greece
    Posts
    4

    Re: Graph Theory Prove Problem (Please help)

    The n-hypercube graph, also called the n-cube graph and commonly denoted Q_n or 2^n, is the graph whose vertices are the 2^k symbols epsilon_1, ..., epsilon_n where epsilon_i=0 or 1 and two vertices are adjacent iff the symbols differ in exactly one coordinate.

    Graph Theory Prove Problem (Please help)-screen-shot-2018-05-30-5.52.26-pm.png
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    Re: Graph Theory Prove Problem (Please help)

    Quote Originally Posted by taleporos View Post
    The n-hypercube graph, also called the n-cube graph and commonly denoted Q_n or 2^n, is the graph whose vertices are the 2^k symbols epsilon_1, ..., epsilon_n where epsilon_i=0 or 1 and two vertices are adjacent iff the symbols differ in exactly one coordinate.

    Click image for larger version. 

Name:	Screen Shot 2018-05-30 at 5.52.26 PM.png 
Views:	1 
Size:	24.9 KB 
ID:	38776
    Ok, so then you simply need to describe the way to count the number of Qk cubes. Because the set of $2^n$ will include differences that are fixed on the $n-k$ coordinates that we are not considering as the subcube and change on exactly one coordinate among the remaining $k$ coordinates, this is a straightforward application of the product principle.

    So, it is the product where we choose the $k$ coordinates for the Qk subcube (there are $\dbinom{n}{k}$ ways to choose them). Independent of that choice, we have $n-k$ remaining coordinates, and those coordinates can be any fixed set of coordinates for a given Qk cube. There are $2^{n-k}$ ways to fix those coordinates. By the Product Principle, the total number of subcubes of dimension k will be $\dbinom{n}{k}2^{n-k}$
    Thanks from taleporos
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Dec 16th 2015, 11:10 AM
  2. Graph theory: Prove min degree(G_n) >= k
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 9th 2011, 09:26 PM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 1st 2011, 04:30 AM
  4. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 18th 2010, 09:36 PM
  5. Replies: 0
    Last Post: Apr 26th 2009, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum