**Homework
Hints**

Chapter 1 hints.

Homework hints for section 1.1:

#5--
The book wasn’t clear if there must be both a directed path from a
vertex *x* to a vertex *y * and
one going from *y * to *x*, or if it suffices to just be *some*
path between them irregardless of which vertex it goes to and from.
These are two different problems, the latter being easier than the
former. I will discuss
the reason for the minimum lengths in class.

#31—what he wants is for you to draw a rectangle for each vertex so that two rectangles overlap if and only if their two vertices are adjacent.

#32—this one didn’t work for me. I would be really interested if anyone can figure it out and explain it to me.

Hints for 1.3:

# 2 d. There are two ways of defining s(x). You can either count the vertex x itself as being adjacent to at least one it neighbors, or you can assume that s(x) is the number of vertices that you can get to from x by a path of length two, without doubling back. The two different definitions of s(x) give two different answers to this problem.

# 6. Forget playing 3 games in the other conference-you should be able to show that 13 teams can't even play 11 games each against on another.

Hints for 1.4

#1. Book answer is missing 1 edge in part a, and two edges in part b. There should be an edge in the dual for every edge in the original graph.

Chapter 2 hints.

2.1

#8: try by way of contradiction

#10: put a vertex in each square, and an edge between vertices a knight’s move apart. Look at vertex degrees.

#16: count vertex degrees in L(G).

2.2

#18 b: start with the circuit in L(G) corresponding to the Hamiltonian circuit in G, then see if you can add the in the vertices in L(G) corresponding to all the edges incident to one vertex in G, then all the ones incident to another, and so on.

2.3

#10: You are not allowed to have one circle exactly overlap another (same circle).

#15: Feuding mathematicians in hotels is kind of bogus. A much more realistic example (and trust me, I’ve run into this one more times than I care to remember) is watching the mother of the bride try to assign the seating arrangements for the 6 tables at the wedding reception. Can’t put smokers with non-smokers, can’t put Uncle Ralph the rabid liberal at the same table as Cousin Fred the Rush Limbaugh ditto-head, can’t put Aunt Ethel at the same table with her brother-in-law, because she drinks, and he thinks it’s funny and just eggs her on until there’s a scene, don’t want to Mr. Paulson the aggressive atheist at the same table as sweet old Father Joe, etc., etc.---you get the picture. This situation has another restriction not mentioned in the hotel example, namely that you have only a set number of seats at each table.

2.4

#6: n here is the number of vertices. Note that in a coloring, the vertices all of one color form an independent set.

#9 b: use 6a and the correspondence between and independent set in G and a complete graph in the complement of G.