Prove a DAG can be obtained by an undirected graph's longest cycle

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

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 κ:

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.

graph-theory proof-writing hamiltonian-path orientation directed-graphs

share|cite|improve this question

asked Jul 17 at 16:02

Gabriel Rebello

1011

add a comment | 

up vote
0
down vote

favorite

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 κ:

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.

graph-theory proof-writing hamiltonian-path orientation directed-graphs

share|cite|improve this question

asked Jul 17 at 16:02

Gabriel Rebello

1011

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

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 κ:

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.

graph-theory proof-writing hamiltonian-path orientation directed-graphs

share|cite|improve this question

asked Jul 17 at 16:02

Gabriel Rebello

1011

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 κ:

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.

graph-theory proof-writing hamiltonian-path orientation directed-graphs

share|cite|improve this question

asked Jul 17 at 16:02

Gabriel Rebello

1011

share|cite|improve this question

share|cite|improve this question

asked Jul 17 at 16:02

Gabriel Rebello

1011

asked Jul 17 at 16:02

Gabriel Rebello

1011

asked Jul 17 at 16:02

Gabriel Rebello

1011

1011

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
2
down vote

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.

share|cite|improve this answer

answered Jul 17 at 16:08

Henning Makholm

226k16291520

• 
  
  
  

  
  

  
  
  
  
  
  

  
  This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness?
  – Gabriel Rebello
  Jul 20 at 18:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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.
  – Henning Makholm
  Jul 20 at 19:03
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – Gabriel Rebello
  Jul 20 at 19:38
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854644%2fprove-a-dag-can-be-obtained-by-an-undirected-graphs-longest-cycle%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

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.

share|cite|improve this answer

answered Jul 17 at 16:08

Henning Makholm

226k16291520

• 
  
  
  

  
  

  
  
  
  
  
  

  
  This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness?
  – Gabriel Rebello
  Jul 20 at 18:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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.
  – Henning Makholm
  Jul 20 at 19:03
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – Gabriel Rebello
  Jul 20 at 19:38
  

  
  
  
  

add a comment | 

up vote
2
down vote

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.

share|cite|improve this answer

answered Jul 17 at 16:08

Henning Makholm

226k16291520

• 
  
  
  

  
  

  
  
  
  
  
  

  
  This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness?
  – Gabriel Rebello
  Jul 20 at 18:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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.
  – Henning Makholm
  Jul 20 at 19:03
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – Gabriel Rebello
  Jul 20 at 19:38
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

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.

share|cite|improve this answer

answered Jul 17 at 16:08

Henning Makholm

226k16291520

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.

share|cite|improve this answer

answered Jul 17 at 16:08

Henning Makholm

226k16291520

share|cite|improve this answer

share|cite|improve this answer

answered Jul 17 at 16:08

Henning Makholm

226k16291520

answered Jul 17 at 16:08

Henning Makholm

226k16291520

answered Jul 17 at 16:08

Henning Makholm

226k16291520

226k16291520

• 
  
  
  

  
  

  
  
  
  
  
  

  
  This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness?
  – Gabriel Rebello
  Jul 20 at 18:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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.
  – Henning Makholm
  Jul 20 at 19:03
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – Gabriel Rebello
  Jul 20 at 19:38
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness?
  – Gabriel Rebello
  Jul 20 at 18:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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.
  – Henning Makholm
  Jul 20 at 19:03
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – Gabriel Rebello
  Jul 20 at 19:38
  

  
  
  
  

This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness?
– Gabriel Rebello
Jul 20 at 18:49

This looks like an algorithm. Is it enough for as a proof? How should I prove its correctness?
– Gabriel Rebello
Jul 20 at 18:49

@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.
– Henning Makholm
Jul 20 at 19:03

@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.
– Henning Makholm
Jul 20 at 19:03

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?
– Gabriel Rebello
Jul 20 at 19:38

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?
– Gabriel Rebello
Jul 20 at 19:38

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854644%2fprove-a-dag-can-be-obtained-by-an-undirected-graphs-longest-cycle%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email