CMI2016-B-3

Question

An undirected graph canbe converted into a directed graph by choosing a direction for every edge. Here is an example:

Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.