Solutions 10
------------

8.3: 

40: Not isomorphic. The left graph has 4 vertices of degree 3, the
    right one only 2. 

42: Not isomorphic. If you select all vertices that have degree 4 in
    both given graphs, and all edges that link such vertices, the lower
    one gives you 2 isolated points, the upper one 2 points with an
    edge between them. These are not isomorphic, hence the two big
    ones are not either.

46: Suppose phi is a way of identifying vettices of G with vertices of
    H such that 2 vertices v, v' are linked precisely when phi(v) and
    phi(v') are linked. Put in another way, v and v' fail to be linked
    if and only if ph(v) and phi(v') fail to be linked.
    Now, failing to be linked in G means to be linked in the
    complement G'. Also, failing to be linked in H means to be linked
    in the complement H'. 
    We conclude that 
    v and v' are linked in G'   
      if and only if
    v and v' are not linked in G
      if and only if 
    phi(v) and phi(v') are not linked in H
      if and only if 
    phi(v) and phi(v') are linked in H'.
    Hence the same map phi gives an isomorphism between the
    complements G' and H'. 

9.4: 

14: a) One component is formed by 
    the vertices a, b, e and the edges between them. There are 2 more
    components, c alone is a "sink"
    (no arrows coming out), and d alone is a "source" (all arrows coming out). 
    b) One component is c,d,e. There are 3 more, the points a, b and f
    taken separately. 
    c) e is a sink, so a component by itself. All other points belong
    to one big strongly connected component.
    
22: G=K_(3,3) is bipartite. That means we can color G with 2 colors
    red and blue. Let v be any vertex of G, and v' an adjacent vertex.
    So, for example, v is red and v' is blue. There cannot be a path
    of even length from v to v' because an even number of steps brings
    you back to the same color. To find the number of paths of length
    3 from v to v' note that this means simply picking one vertex on
    the blue side as the end point of the first edge, and a vertex on
    the red side as endpoint of the second edge. (All red vertices
    are linked to all bue ones, so there is no problem of "getting
    stuck"). 
    Then this means that there are 3x3=9 paths of length 3.
    If we look at paths of length 5, we need to look at 4 intermediate
    points, 2 red and 2 blue. So there are 3^4 ways of making a path
    from v to v' that have length 5.

26: Note first that whenever you have a graph G with k components, and
    you remove one edge, then you can have either k or k+1 components
    in the new graph. 
    Starting with a connected graph G, delete all e edges. 
    Since G had only one connected component, G with all edges deleted
    has no more than 1+e connected components.  
    On the other hand, G without all edges has as many connected
    components as G has vertices.
    So v is at least e+1. Put another way, if G is connected then the
    number of edges is at least one less than the number of vertices.

28: We saw a theorem that says that if G has ay vertex of odd degree
    then there must be another one of odd degree (in fact, we proved that
    the number of vertices of odd degree is even. So if there is one,
    there must be at least 2.)
    Now let v be of odd degree and denote by H the connected component
    of v in G. Then H is of course a graph in its own light. That
    means, that the theorem about the existence of even numbers of odd
    degree vertices applies to H just as much as to G. So there is a
    vertex v' (different from v) in H that has odd degree. (Maybe more
    than one even.)  But since H is connected, there is a path from v
    to v'. 

44: It is a block matrix with sizes of the blocks equal to the number
    of vertices in the respective connected components. 

46: Consider the (i,j)-entry of the successive powers A, A^2,
    A^3,... where A is the adjacency matrix of G. The first time that
    this entry is nonzero indicates the shortest path from v_i to v_j.

54: a) (fwsc,0) (fws,c) (fwc,s) (fsc,w) (0,fwsc) (w,fsc) (s,fwc)
       (c,fws) (fs,wc) (wc,fs) (0,fwsc).
    b) This is a bit tricky in a text file.
    c) It encodes a strategy for the farmer to get his family acrosss
       the river.
    d) (fwsc,0) (wc,fs) (fwc,s) (c,fws) (fsc,w) (s,fwc) (fs,wc) (0,fwsc)
       and
       (fwsc,0) (wc,fs) (fwc,s) (w,fsc) (fsw,c) (s,fwc) (fs,wc) (0,fwsc)
    e) Obviously, it makes no difference. Wolf and cabbage cross once
       in each scenario and sheep crosses 3 times both times.