I have this question I need to solve:
Let G be the graph whose vertex set is $\{0,1\}^6$ and which has an edge between two 6-tuples if and only if these tuples differ at exactly one place. How many connected components does this graph have?
My and a friend of mine have both been trying to solve this (separately) but we both get different answers. I got the answer "1" and he got "2".
My argument is that since each number in a tuple can be flipped (1 -> 0 and 0-> 1) there must exist another vertex (the tuple with the flipped number), that can be connected with an edge, for each number in the tuple, thus each vertex can connect to at least one other vertex (first vertex can connect to 6 other vertices and those vertices can each connect to 5 other vertices and so on).
Thus my conclusion is that the entire graph has to be connected. In other words, the amount of components is "1".
I have no idea how my friend managed to get "2". Who is right here? Are we both wrong? Is there a more methodical way to solve this?
Thanks!
I would be a bit cleaner with your wording. As Marcus M's comment suggests, if your hunch is that the graph is connected, i.e. has $1$ component, then it suffices to notice that there is a path from $(000000)$ to any other $6$-tuple. This can be achieved by flipping $0$s one at a time until the desired $6$-tuple is reached. As every $6$-tuple can be reached from $(000000)$, there is a path between every pair of vertices $v,w$ (travel from $v$ to $(000000)$ to $w$), and so our graph is connected.
This is a special case of the Hypercube Graph. There are many more interesting exercises involving it.
To end off with a following exercise, your friend would be correct had you constructed your graph where two $6$-tuples are joined by an edge if they differ in exactly $2$ positions.