Let G(V, E) be a finite undirected graph and let κ be its longest undirected cycle.

  1. 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.
  2. 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 κ:

enter image description here

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.


Assign different numbers as labels to the vertices, such that your chosen cycle visits vertices in increasing order.

It doesn't matter which labels you choose for vertices that are not in your cycle, as long as the labels are all distinct.

Orient each edge in the direction of increasing numbers.

  • $\begingroup$ This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness? $\endgroup$ – Gabriel Rebello Jul 20 '18 at 18:49
  • $\begingroup$ @GabrielRebello: It is probably not enough for an actual proof in most classroom contexts, but it contains the main idea of a proof. I'm leaving the filling-in of proof details to you, but it is a quite simple verification that the orientation that results will have the properties you want. $\endgroup$ – Henning Makholm Jul 20 '18 at 19:03
  • $\begingroup$ Thanks @HenningMakholm. I'm completely new into verifications so I'm willing to learn. Is there a good reference for this kind of problem that I can use to start writing and understanding the proof? $\endgroup$ – Gabriel Rebello Jul 20 '18 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.