Let G(V, E) be a finite undirected graph and let κ be its longest undirected cycle.
- Prove that it is always possible to obtain an orientation ω(κ) in which κ is topologically sorted and hence its last edge (from node 1 to node N) is inverted.
- Prove that given ω(κ) it is always possible to orient the remainder of the graph as to build a DAG.
For example, in a 5-node graph with its hamiltonian path as κ:
The proof of (1) seems intuitive: one can always direct the edges of an undirected cycle as to form a directed cycle and then invert one of the edges at random. This causes a topological sort starting at the node on the origin of the new edge. I have no clue on the proof of (2). I'm new to graph theory and still lack the knowledge to write proofs formally, so I'm hoping to learn a bit more on this with this question too.
Thanks in advance.