Solutions 9.

9.1.

16: I can't really draw this on the computer. The graph has one vertex
    for each person and then one edge for each acquaintance.

20: Team 4 beat 3, but was beaten by everyone else.

9.2:

36: a) No. If the graph is simple, there can be no multiple edges. So
    the last vertex is linked to 5 different other vertices. Since there
    are only 5 others to begin with, each vertex has at least one edge
    coming in. Hence there is no vertex of degree zero.
    b) No. There are not enough vertices to have a degree 6 vertex.
    c) Possible. A hexagon.
    d) No. The sum of the suggested degrees is 15, which is not even.
    e) Yes. A hexagon with a diagonal.
    f) Yes. Three linked pairs.
    g) Yes. A hexagon with 3 diagonals, all emanating from one vertex.
    h) No. Each vertex of degree 5 ought to be linked to all other
    vertices, but then none can have degree 1.

26: a) If n is 1 or 2. All other K_n contain a triangle.
    b) If n is even.
    b) If n=1 or 2, a, all other W_n contain a triangle.
    c) For all n. Suppose the vertices have coordinates 0 or 1 in each
    component. Color a vertex red if the coordinate sum is even, color
    it blue otherwise. Adjacent vertices are always pairs of an odd
    and an even sum, so the coloring works.

44: 4 with one vertex, (4 choose 2)*2^1 with 2 vertices, 
    (4 choose 3)*2^3 on 3 vertices, and (4 choose 4)*2^6 on 4 vertices.

46: Let v be the number of vertices.
    From class we know a theorem that says that the sum of all
    degrees is twice the sum of the edges. Since each degree is at
    most M, the sum of v copies of M will be at least as large as the
    sum of the degrees. So M*v is at least 2e. That does part b). Part
    a) is completely similar.

48: When m=n, because the degree of m of the vertices is n, while the
    degree of n of the vertices is m. 

9.3. :

16: This is fairly easy.
    
20: 1 1 1 1
    0 1 0 1
    1 0 1 0
    1 1 1 1

25: Yes. One can recover the graph from the matrix by putting down n
    vertices (as many as the matrix has rows) and then linking
    vertices if the (i,j)-entry of the matrix is a 1. 

30: The incidence matrix lists (in rows) a "1" if the fixed vertex is
incident to the edge in question and "0" otherwise. Summing these
entries for a fixed vertex gives the degree of the vertex.