Graph Theory – N-Cube

The n-cube (denoted as Qn) is the graph whose vertex set is the set of 2n binary n-tuples, with two n-tuples adjacent if they differ in exacly one coordinate (e.g. 01011 and 01001 are adjacent).

Here are drawings of Q1, Q2, Q3.

imageimage

image

How many edges are there in Qn?

Prove that Qn is Bipartite.