Proof n-cube graph is connected

Question

I am studying graph theory and my text book gives a proof for an n-cube graph being connected that I find really weird/confusing. Is there a simpler proof to show that the n-cube is connected.

The n-cube graph is the graph where the vertices {0,1} strings of length n. Two strings are adjacent if they differ is exactly one position.

For example the 2-cube graph has vertices V:{00, 01, 10, 11} and edges: (00 <-> 01), (00 <-> 10), (01 <-> 11), (10 <-> 11)

This is simply a square. What kind of proof can I use show that it is connected? I am currently thinking induction.

My rough try at a Proof

Proof By Induction

Base Case ( n=1 ) Then graph has two vertices, 0 & 1 which are connected (since they differ by one). Assume than P(n) is true. Prove P(n+1). Lets remove the last digit. From the inductive hypothesis we know that P(n) is connected. Add the last digit back in. We can partition P(n+1) into $A_0$ which contains all the vertices with a 0 as the last digit; $A_1$ which contains all the vertices with 1 as the last digit. Since $A_0$ and $A_1$ are essentially P(n), we know they are connected from the inductive hypothesis. Since $A_0$ and $A_1$ are connected we can conclude that P(n+1) is connected!

Is this correct?

Answer 1

Here's a full proof as outlined above.

The $1$-cube graph is connected by inspection. (You could even do the $0$-cube graph, which is automatically connected, as it only has one vertex.) Now assume that the $n$-cube graph is connected. In the $(n+1)$-cube graph, consider the subgraphs consisting of those vertices with final digit $0$ and $1$ respectively (and all edges between them); call these $A_0$ and $A_1$. Then $A_0$ and $A_1$ are isomorphic to the $n$-cube graph, thus connected by hypothesis. Now note that there is an edge between $(0,\dots,0)$ and $(0,\dots,1)$ as they differ by a single digit.

So the $(n+1)$-cube graph is connected; for pick any vertices $p$ and $q$ in the graph. If they are both in $A_0$ or $A_1$ they are connected by inductive hypothesis; so suppose WLOG $p$ is in $A_0$ and $q$ is in $A_1$. There is a path connecting $p$ to $(0,\dots,0)$ and a path connecting $(0,\dots,1)$ to $q$ by inductive hypothesis. Connect these paths by including the edge between $(0,\dots,0)$ and $(0,\dots,1)$ and we've constructed a path connecting $p$ and $q$, as desired.

Answer 2

Your proof may be correct but it is weird/confusing. There is a simpler proof that the $n$-cube is connected. A graph is connected if there is a path from any vertex to any other vertex. In terms of the $n$-cube, that just means that you can get from one $\{0,1\}$-string of length $n$ to another one by changing one bit at a time. Which is so obvious that there is no point in writing a detailed proof.

Answer 3

proof by construction. any two nodes, pairwise different, noted by -, if same, noted by . then any two nodes, the difference are noted as --.--.--.-- then one is --0--1--0--1--, the other is --1--0--1--0-- then there is edges between between --0--1--0--1-- and --1--1--0--1-- between --1--1--0--1-- and --1--0--0--1-- between --1--0--0--1-- and --1--0--1--1-- between --1--0--1--1-- and --1--0--1--0-- then there is a path betwen --0--1--0--1-- and --1--0--1--0--

so, there is path between any two node, so graph is connected.