Hypercube graph

Let Q_n be the hypercube graph.

  • Q_1 = K_2 (the complete graph with two vertices),
  • Q_2 = C_4 (the square), and
  • Q_n is constructed taking two copies of Q_{n-1} and adding an edge that connects each vertex of the first copy with the corresponding vertex of the second copy.

Easy: Find \chi(Q_n) (chromatic number) for every n.

Harder: Find every n such that Q_n is planar.

 

Advertisements
Hypercube graph

One thought on “Hypercube graph

  1. gciruelos says:

    Q_n is bipartite for every n, so its chromatic number is 2. (Prove that it is bipartite).

    Now, for the planarity problem, first let’s observe that Q_n is triangle free for every n (easy to show), so then if it is planar, we can use Euler’s formula: v - e + f = 2. Let’s assume e \geq 4, then for every face we have at least 4 edges, then we have that \frac{4f}{2} < e (because we are counting every edge twice. Then, joining this with Euler's formula we get that v < \frac{e}{2} + 2.

    We can check by hand that Q_1, Q_2 and Q_3 are planar.
    For Q_n with n \geq 4, if it was planar, we should have that v < \frac{e}{2} + 2. It is easy to calculate by induction the number of edges and vertices of Q_n for all n and check that that doesn't happen.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s