2. An n-cube is a graph in which each vertex is a string of n symbols, each a ze

Question

2. An n-cube is a graph in which each vertex is a string of n symbols, each a zero or a one. Two vertices are connected with an edge if they differ in exactly one place. For example, the 2-cube is shown below.

a. Draw the diagrams of the 1-cube and 3-cube. Clearly explain why these diagrams correspond to 1-cube and 3-cube with the definition given above.

b. Explain how you can construct a 4-cube out of two 3-cubes, both in terms of the string definition and visually. Again, clearly explain the correspondence between the two representations.

c. Conjecture formulas for the number of vertices and edges in an n-cube.

d. Using your conjectured formulas, can you come up with a way to “define” 0-cube so that it fits your conjectures?

e. Officially prove your conjectured formulas for n 1 using mathematical induction.

a. I looked these up to check my answer, and I got them right. So I get that much.

b. Basically I added a 1 to the end of each 3-string, and then a 0 to each 3-string. This effectively creates two 3-cubes. Then you can connect all of the strings that differ by one to get a 4-cube.

Visually, you can draw those each as 3-cubes, and then connect all corresponding vertices. So I also get that much.

c. Vertices: 2n   Edges: 2n-1*n

d. A 0 cube would literally just be one vertex with a string of size 0.

e. This is where I'm struggling. My professor gave us the hint, (Make sure you see how a size n cube is visualized inside the next size, (n+1)-cube for your proofs), but I don't see how that helps. I feel like the 4-cube becomes 4-dimensional so I have no idea how to visualize it. Can someone help me with this proof please?

Explanation / Answer

The conjecture formulae are:

Vertices = 2n

Edges = (2n-1) * n

For n=1,

Vertices = 2*1 = 2 (i.e 0 and 1)

Edges = (21-1) =1. (One edge connecting 0 and 1)

Let us assume this is true for some n=k.

Vertices = 2k

Edges = (2k-1) * k

We shall now prove that this holds true for k+1 as well.

A k+1 cube has vertices which are strings of k+1 symbols. These can be obtained by appending 0s and 1s to the vertices of a k cube.

Total no of vertices for a k cube = 2k.

Total no of vertices with 0s appended = 2k

Total no of vertices with 1s appended = 2k

=> Total no of vertices for a k+1 cube = 2k + 2k = 2 * 2k = 2k+1

Now let us look at edges. Each vertex of a k+1 cube has symbol length k+1.

=> Number of vertices with one symbol changed = k+1.

But it is given that an edge is formed when two vertices with one symbol changed are connected.

=> Number of edges of k+1 cube = (Number of vertices of k+1 cube) * (k+1)/2 (Each edge will be repeated twice)

=> Number of edges of k+1 cube = 2k+1 (k+1) /2 = 2k (k+1) = 2(k+1)-1 (k+1)

which proves the conjecture.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.