Problem 1. The vertices of any directed graph may be partitioned into strongly connected components. Two vertices i and j belong to the same strongly connected component if there is some path from i to j and some path from j to i. Theory pig notices an interesting phenomenon. He starts with a graph and partitions it into strongly connected components. He then removes all edges which connect two vertices contained in the same component, and notices that the graph which remains has no cycles. Prove that this will always be true.

Solution:

Proof. Proof by contradiction Consider an arbitrary graph G = (V, E). Let G′ = (V, E′) be the graph which remains when all edges of G connecting two vertices in the same strongly connected component are removed.

Suppose that G′ has a cycle. Let i_{1}, i_{2}, ..., i_{k} denote the nodes in this cycle. We know that there is i_{1} a path from i_{1} to i_{2}, since they are connected in a cycle. Similarly, we know there is a path from i_{2} to i_{1}. However, this implies that i_{1} and i_{2} should have been in the same strongly connected component in G, and the edge from i_{1} to i_{2} should have been removed when forming G′. Since the edge was not removed, we have a contradiction, which implies that G′ has no cycles.