Math 344: Introduction to Combinatorics

Comments on Homework: Section 2.2

Theorem 3

Question

I have another question in dealing with theorem 3 for 2.2. In the notes, if there is a Hamilton circuit then (4-2)(R₄ - r₄) + (6-2)(R₆-r₆) = 0 or (R₄-r₄) + 2(R₆-r₆) = 0. Now in your graph the number of regions with 4 boundary edges is r₄+ R₄ = 3. So the sum of this is ODD, but the difference r₄-R₄ = -2(R₆-r₆) = 0 is EVEN. This implies that no possible Hamilton circuit exists.

What is going on here? Is it b/c both are not even or odd together? Could you please explain the concept further?

Answer

Sure. So we have

R₄ - r₄ = odd
R₄ + r₄ = even

Add these two equations (and notice that odd+even = odd):

2R₄ = odd.

But the left-hand side is even, and the right-hand side is odd! This is impossible, so we have a contradiction.

That is: if there's a Hamilton circuit, then everything above works, and 2R₄ is odd. This is wrong, so there can't be a Hamilton circuit.

Problem 8

Question

Regarding part (b), we have r₃ + r'₃=2 and r₆ + r'₆=2. We have to prove the following is wrong:
(3-2)(r₃ - r'₃) + (6-2)(r₆ + r'₆)=0
if and only if (r₃ - r'₃) + 4(r₆ - r'₆)=0
This only happens when r₃=r'₃=1 and r₆ = r'₆ =1.

Answer

You've forgotten one region. That is, there are five regions in the picture -- you haven't counted the one outside the graph.

Problem 9

Question

Could you give me some hints about solving parts (a) and (b)?

Answer

Hint: draw some bipartite graphs, some with the two sets of vertices close to the same size, and some with the two sets of vertices of very different sizes. Which ones have Hamilton paths? What can you say about the sizes of vertex sets if there is a Hamilton path?

Problem 18

Question

Could you give some hint about solving this problem?

Answer

Use question 9. That is, the cube graph is bipartite. How many small cubes are in each vertex set?