Here are some answers for the exercises.

1. Number 2 and 3 have an Eulercycle. The others don't, because they have nodes with an odd number of edges.

The Eulercycle in graph 2 is trivial (the only cycle).

An Eulercycle for graph 3 can be constructed as follows: Start at the top, and go around the outer edges full circle. Then, draw the pentagramstar, ending up where you started.

2. There is no Eulerpath because there are two nodes A, B, with degree 3. Since all other nodes have an even degree, adding one more edge between A and B must mean that there is an Eulercycle. We get the Eulerpath by finding the Eulercycle with the extra edge, and then removing it. In other words, the Eulerpath must start and finish with a node with an odd degree.

3. (a.) The number of components afterwards can either be 1 (the graph is still connected) or 2 (the graph was split into two components). Example for both: (1) G has three points with edges between each pair of points. (2) G has two points with one edge between.

(b.) The number of components afterwards can be anything: 0, 1, 2, 3, ... To see this, we will construct a graph G(k) that will fall apart into k components after removing one node v (you can choose k!). G(k) has one node v, plus k extra nodes. Each extra node has an edge to v. If we remove v, and all the edges connected to v, the number of components is exactly k.

4. R is reflexive: There is always a path from v to v for any node v (the empty path).

R is symmetric: If we have a path from u to v, then we also have a path from v to u (just take the reverse of the path).

R is transitive: If we have a path from u to v, and a path from v to w, we also have a path from u to w (glue the two paths together, with v in the middle).

5. We do this by strong induction on n.

Base case: n=1. A tree with 1 node has no edges. OK.

Step case: n>=2.

The I.H. says that, for all 1 <= k < n, trees with k nodes have k-1 edges.

Now, we take a tree T with n nodes. There must be at least 2 nodes u and v (because n >= 2) and 1 edge e (because T is connected).

Now, remove the edge e.

The resulting graph consists of two separate components; one connected to u and one connected to v. (There cannot be more than two components, since every node is still either connected to u or to v. There cannot be one component, since that would mean there is still a path between u and v, which means that there was a cycle in T.)

Each component (by definition) is connected, and also has no cycle (because there are no cycles in T). So each component is a tree. Also, each component has less nodes than n, since each side has at least one node.

By the induction hypothesis, each component has 1 edge less than there are nodes. This means that the total number of edges for both components is n-2. This was after we removed one edge from T, so T has n-1 edges.

6. We do this by strong induction on the length of the path n.

Base case: n=0. The path is already simple. OK.

Step case: n>=1.

The I.H. says that for all u, v, if there is a path of length k between u and v, there also exists a simple path between u and v.

Suppose that we have u and v with a path of length n. Either it is a simple path (in which case we are done), or it is not. If it is not, then there must be a node w that appears twice in the path. The path thus looks something like: u--P--w--Q--w--R--v. Here, P, Q, R are paths going from u to w, w to w, and w to v, respectively. (Note that P and/or may be empty, in which case u=w or v=w.)

Look at the path: u--P--w--R--v. It is certainly shorter than n, because we removed at least one step (the one involving w). So, by the I.H., there must be a simple path from u to v.

7. Proof by contradiction. Suppose we have a graph G with nodes u and v, two different simple paths from u to v, and no cycles.

Consider the subgraph G' that consists of exactly the two paths (the nodes and edges) between u and v. Clearly, G' is connected. Also, G' does not contain any cycles. So, G' is a tree. However, we know that in a tree, there exists only one unique simple path from u to v. This is a contradiction with our assumption.

(For a more direct proof, see page 193 in the book.)

8. 7.8 does not have a topological ordering, because there is a cycle: a->c->a.

7.9 does have a topological ordering. For example, 1, 2, 3, 4, 5, 6, 7, 8.

9. A cycle means that you can make a profit out of nothing, by buying one currency on the cycle, and then selling it for the next currency, until we get back to the beginning.

In reality, we have to be very quick, because market prices adapt to arbitrageurs from all over the world exploiting this very cycle!

10. There are 7 topological orderings: ABCGDEF, ABGCDEF, ABGDCEF, AGBCDEF, AGBDCEF, GABCDEF, GABDCEF.

We can get these by the following observation. First, we must choose between A or G as the first node. If we pick G, the next choice comes between C and D: 2 possibilities. If we pick A as the first node, we can either pick B or G as the first node. If we pick B, there are 3 possibilities. If we pick G, there are 2. 2+3+2=7.

11. R is reflexive.

R is not symmetric. Consider the graph A->B, for which we have R(A,B) but not R(B,A).

R is transitive.