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.





#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).






#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.





#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.







#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.