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.