Mixing
There exists a permutation $(A_1, ldots , A_n)$ of the vertices $V ={1,ldots,n}$ such that for all...
Let $G = (V,E)$ be a directed graph on $n$ vertices, $V = {1, ldots,n}$, such that for every pair of distinct vertices $i, j in V$, exactly one of the two possible directed edges $(i, j)$ or $(j, i)$ is in the edge set $E$ (but not both). Prove that there must exist a permutation $(A_1, ldots, A_n)$ of the vertices $V ={1, ldots,n}$,such that for all $iin {1, ldots,n−1}, (A_i,A_{i+1})in E$.
I can think of how it is true but got stuck on proving it. Could anyone please help?
combinatorics discrete-mathematics graph-theory directed-graphs
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
asked Nov 20 '18 at 19:58
yorkliang
61
add a comment |
Let $G = (V,E)$ be a directed graph on $n$ vertices, $V = {1, ldots,n}$, such that for every pair of distinct vertices $i, j in V$, exactly one of the two possible directed edges $(i, j)$ or $(j, i)$ is in the edge set $E$ (but not both). Prove that there must exist a permutation $(A_1, ldots, A_n)$ of the vertices $V ={1, ldots,n}$,such that for all $iin {1, ldots,n−1}, (A_i,A_{i+1})in E$.
I can think of how it is true but got stuck on proving it. Could anyone please help?
combinatorics discrete-mathematics graph-theory directed-graphs
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
asked Nov 20 '18 at 19:58
yorkliang
61
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 '18 at 20:05
Start with a base case where you have 2 vertices, show that it works, use induction over the number of vertices.
– B.Swan
Nov 20 '18 at 20:19
1
Furthermore, there is a unique permutation $(A_1,A_2,ldots,A_n)$ such that $(A_1,A_2,ldots,A_n)$ forms a directed path in $G$ iff $G$ has no directed cycles (i.e., a closed path $(v_1,v_2,ldots,v_l,v_1)$, where each $v_{i}v_{i+1}$ is an arc in $G$ for $i=1,2,ldots,l-1$, and $v_lv_1$ is also an arc in $G$). Equivalently, there exists a permutation $(A_1,A_2,dots,A_n)$ of vertices such that the in-degree of $A_i$ is $i-1$ for each $i=1,2,dots,n$. Equivalently, the relation $to$ on $V$ defined by $$uto v$$ iff there is a directed path in $G$ from $u$ to $v$ is an order relation on $V$.
– Batominovski
Nov 20 '18 at 21:04
add a comment |
Let $G = (V,E)$ be a directed graph on $n$ vertices, $V = {1, ldots,n}$, such that for every pair of distinct vertices $i, j in V$, exactly one of the two possible directed edges $(i, j)$ or $(j, i)$ is in the edge set $E$ (but not both). Prove that there must exist a permutation $(A_1, ldots, A_n)$ of the vertices $V ={1, ldots,n}$,such that for all $iin {1, ldots,n−1}, (A_i,A_{i+1})in E$.
I can think of how it is true but got stuck on proving it. Could anyone please help?
combinatorics discrete-mathematics graph-theory directed-graphs
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
asked Nov 20 '18 at 19:58
yorkliang
61
Let $G = (V,E)$ be a directed graph on $n$ vertices, $V = {1, ldots,n}$, such that for every pair of distinct vertices $i, j in V$, exactly one of the two possible directed edges $(i, j)$ or $(j, i)$ is in the edge set $E$ (but not both). Prove that there must exist a permutation $(A_1, ldots, A_n)$ of the vertices $V ={1, ldots,n}$,such that for all $iin {1, ldots,n−1}, (A_i,A_{i+1})in E$.
I can think of how it is true but got stuck on proving it. Could anyone please help?
combinatorics discrete-mathematics graph-theory directed-graphs
combinatorics discrete-mathematics graph-theory directed-graphs
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
asked Nov 20 '18 at 19:58
yorkliang
61
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
asked Nov 20 '18 at 19:58
yorkliang
61
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
edited Nov 20 '18 at 20:48
Batominovski
33.8k33292
33.8k33292
asked Nov 20 '18 at 19:58
yorkliang
61
asked Nov 20 '18 at 19:58
yorkliang
61
asked Nov 20 '18 at 19:58
yorkliang
61
61
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 '18 at 20:05
Start with a base case where you have 2 vertices, show that it works, use induction over the number of vertices.
– B.Swan
Nov 20 '18 at 20:19
1
Furthermore, there is a unique permutation $(A_1,A_2,ldots,A_n)$ such that $(A_1,A_2,ldots,A_n)$ forms a directed path in $G$ iff $G$ has no directed cycles (i.e., a closed path $(v_1,v_2,ldots,v_l,v_1)$, where each $v_{i}v_{i+1}$ is an arc in $G$ for $i=1,2,ldots,l-1$, and $v_lv_1$ is also an arc in $G$). Equivalently, there exists a permutation $(A_1,A_2,dots,A_n)$ of vertices such that the in-degree of $A_i$ is $i-1$ for each $i=1,2,dots,n$. Equivalently, the relation $to$ on $V$ defined by $$uto v$$ iff there is a directed path in $G$ from $u$ to $v$ is an order relation on $V$.
– Batominovski
Nov 20 '18 at 21:04
add a comment |
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 '18 at 20:05
Start with a base case where you have 2 vertices, show that it works, use induction over the number of vertices.
– B.Swan
Nov 20 '18 at 20:19
1
Furthermore, there is a unique permutation $(A_1,A_2,ldots,A_n)$ such that $(A_1,A_2,ldots,A_n)$ forms a directed path in $G$ iff $G$ has no directed cycles (i.e., a closed path $(v_1,v_2,ldots,v_l,v_1)$, where each $v_{i}v_{i+1}$ is an arc in $G$ for $i=1,2,ldots,l-1$, and $v_lv_1$ is also an arc in $G$). Equivalently, there exists a permutation $(A_1,A_2,dots,A_n)$ of vertices such that the in-degree of $A_i$ is $i-1$ for each $i=1,2,dots,n$. Equivalently, the relation $to$ on $V$ defined by $$uto v$$ iff there is a directed path in $G$ from $u$ to $v$ is an order relation on $V$.
– Batominovski
Nov 20 '18 at 21:04
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 '18 at 20:05
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 '18 at 20:05
Start with a base case where you have 2 vertices, show that it works, use induction over the number of vertices.
– B.Swan
Nov 20 '18 at 20:19
Start with a base case where you have 2 vertices, show that it works, use induction over the number of vertices.
– B.Swan
Nov 20 '18 at 20:19
1
1
Furthermore, there is a unique permutation $(A_1,A_2,ldots,A_n)$ such that $(A_1,A_2,ldots,A_n)$ forms a directed path in $G$ iff $G$ has no directed cycles (i.e., a closed path $(v_1,v_2,ldots,v_l,v_1)$, where each $v_{i}v_{i+1}$ is an arc in $G$ for $i=1,2,ldots,l-1$, and $v_lv_1$ is also an arc in $G$). Equivalently, there exists a permutation $(A_1,A_2,dots,A_n)$ of vertices such that the in-degree of $A_i$ is $i-1$ for each $i=1,2,dots,n$. Equivalently, the relation $to$ on $V$ defined by $$uto v$$ iff there is a directed path in $G$ from $u$ to $v$ is an order relation on $V$.
– Batominovski
Nov 20 '18 at 21:04
Furthermore, there is a unique permutation $(A_1,A_2,ldots,A_n)$ such that $(A_1,A_2,ldots,A_n)$ forms a directed path in $G$ iff $G$ has no directed cycles (i.e., a closed path $(v_1,v_2,ldots,v_l,v_1)$, where each $v_{i}v_{i+1}$ is an arc in $G$ for $i=1,2,ldots,l-1$, and $v_lv_1$ is also an arc in $G$). Equivalently, there exists a permutation $(A_1,A_2,dots,A_n)$ of vertices such that the in-degree of $A_i$ is $i-1$ for each $i=1,2,dots,n$. Equivalently, the relation $to$ on $V$ defined by $$uto v$$ iff there is a directed path in $G$ from $u$ to $v$ is an order relation on $V$.
– Batominovski
Nov 20 '18 at 21:04
add a comment |
1 Answer
1
active
oldest
votes
We show it by induction on the number of vertices in the graph $G$.
Base case: when there is only two vertices, the claim is true.
Assume now that for graph with $n$ vertices, the claim is true, we have to show that a graph on $n+1$ vertices, the claim is true.
So let $G$ be a graph on $n+1$ vertices ${v_1,...,v_{n+1}$}. let's look at the vertex $v_{n+1}$,
Case 1:suppose it is adjacent only to outgoing edges. Then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_{n+1},v_1,...,v_n$ is a directed path in $G$.
Case2: Suppose $v_{n+1}$ is adjacent to only ingoing edges, then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_1,...,v_n,v_{n+1}$ is a directed path in $G$.
Case3: Suppose it is not case 1 nor case 2, then again by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Suppose we have edge $(v_1,v_{n+1})$ and for all $i$, we have edges $(v_iv_{n+1})$ and $(v_{i+1}v_{n+1})$ for $1leq i leq n-1$, we are back to case 2. So there must be $1 leq i leq n-1$ such that $(v_i,v_{n+1})$ and $(v_{n+1},v_{i+1})$ are edges in the graph. Well, $v_1,...,v_i,v_{n+1},v_{i+1},...,v_n$ is a hamiltonian directed path! done
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
answered Nov 20 '18 at 20:21
mathnoob
1,799422
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3006810%2fthere-exists-a-permutation-a-1-ldots-a-n-of-the-vertices-v-1-ldots%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
We show it by induction on the number of vertices in the graph $G$.
Base case: when there is only two vertices, the claim is true.
Assume now that for graph with $n$ vertices, the claim is true, we have to show that a graph on $n+1$ vertices, the claim is true.
So let $G$ be a graph on $n+1$ vertices ${v_1,...,v_{n+1}$}. let's look at the vertex $v_{n+1}$,
Case 1:suppose it is adjacent only to outgoing edges. Then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_{n+1},v_1,...,v_n$ is a directed path in $G$.
Case2: Suppose $v_{n+1}$ is adjacent to only ingoing edges, then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_1,...,v_n,v_{n+1}$ is a directed path in $G$.
Case3: Suppose it is not case 1 nor case 2, then again by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Suppose we have edge $(v_1,v_{n+1})$ and for all $i$, we have edges $(v_iv_{n+1})$ and $(v_{i+1}v_{n+1})$ for $1leq i leq n-1$, we are back to case 2. So there must be $1 leq i leq n-1$ such that $(v_i,v_{n+1})$ and $(v_{n+1},v_{i+1})$ are edges in the graph. Well, $v_1,...,v_i,v_{n+1},v_{i+1},...,v_n$ is a hamiltonian directed path! done
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
answered Nov 20 '18 at 20:21
mathnoob
1,799422
add a comment |
We show it by induction on the number of vertices in the graph $G$.
Base case: when there is only two vertices, the claim is true.
Assume now that for graph with $n$ vertices, the claim is true, we have to show that a graph on $n+1$ vertices, the claim is true.
So let $G$ be a graph on $n+1$ vertices ${v_1,...,v_{n+1}$}. let's look at the vertex $v_{n+1}$,
Case 1:suppose it is adjacent only to outgoing edges. Then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_{n+1},v_1,...,v_n$ is a directed path in $G$.
Case2: Suppose $v_{n+1}$ is adjacent to only ingoing edges, then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_1,...,v_n,v_{n+1}$ is a directed path in $G$.
Case3: Suppose it is not case 1 nor case 2, then again by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Suppose we have edge $(v_1,v_{n+1})$ and for all $i$, we have edges $(v_iv_{n+1})$ and $(v_{i+1}v_{n+1})$ for $1leq i leq n-1$, we are back to case 2. So there must be $1 leq i leq n-1$ such that $(v_i,v_{n+1})$ and $(v_{n+1},v_{i+1})$ are edges in the graph. Well, $v_1,...,v_i,v_{n+1},v_{i+1},...,v_n$ is a hamiltonian directed path! done
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
answered Nov 20 '18 at 20:21
mathnoob
1,799422
add a comment |
We show it by induction on the number of vertices in the graph $G$.
Base case: when there is only two vertices, the claim is true.
Assume now that for graph with $n$ vertices, the claim is true, we have to show that a graph on $n+1$ vertices, the claim is true.
So let $G$ be a graph on $n+1$ vertices ${v_1,...,v_{n+1}$}. let's look at the vertex $v_{n+1}$,
Case 1:suppose it is adjacent only to outgoing edges. Then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_{n+1},v_1,...,v_n$ is a directed path in $G$.
Case2: Suppose $v_{n+1}$ is adjacent to only ingoing edges, then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_1,...,v_n,v_{n+1}$ is a directed path in $G$.
Case3: Suppose it is not case 1 nor case 2, then again by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Suppose we have edge $(v_1,v_{n+1})$ and for all $i$, we have edges $(v_iv_{n+1})$ and $(v_{i+1}v_{n+1})$ for $1leq i leq n-1$, we are back to case 2. So there must be $1 leq i leq n-1$ such that $(v_i,v_{n+1})$ and $(v_{n+1},v_{i+1})$ are edges in the graph. Well, $v_1,...,v_i,v_{n+1},v_{i+1},...,v_n$ is a hamiltonian directed path! done
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
answered Nov 20 '18 at 20:21
mathnoob
1,799422
We show it by induction on the number of vertices in the graph $G$.
Base case: when there is only two vertices, the claim is true.
Assume now that for graph with $n$ vertices, the claim is true, we have to show that a graph on $n+1$ vertices, the claim is true.
So let $G$ be a graph on $n+1$ vertices ${v_1,...,v_{n+1}$}. let's look at the vertex $v_{n+1}$,
Case 1:suppose it is adjacent only to outgoing edges. Then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_{n+1},v_1,...,v_n$ is a directed path in $G$.
Case2: Suppose $v_{n+1}$ is adjacent to only ingoing edges, then by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Well now, $v_1,...,v_n,v_{n+1}$ is a directed path in $G$.
Case3: Suppose it is not case 1 nor case 2, then again by induction hypothesis, the graph induced by vertices ${v_1,...,v_n}$ has a directed path, says, $v_1,...,v_n$. Suppose we have edge $(v_1,v_{n+1})$ and for all $i$, we have edges $(v_iv_{n+1})$ and $(v_{i+1}v_{n+1})$ for $1leq i leq n-1$, we are back to case 2. So there must be $1 leq i leq n-1$ such that $(v_i,v_{n+1})$ and $(v_{n+1},v_{i+1})$ are edges in the graph. Well, $v_1,...,v_i,v_{n+1},v_{i+1},...,v_n$ is a hamiltonian directed path! done
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
answered Nov 20 '18 at 20:21
mathnoob
1,799422
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
edited Nov 20 '18 at 20:53
Batominovski
33.8k33292
33.8k33292
answered Nov 20 '18 at 20:21
mathnoob
1,799422
answered Nov 20 '18 at 20:21
mathnoob
1,799422
answered Nov 20 '18 at 20:21
mathnoob
1,799422
1,799422
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3006810%2fthere-exists-a-permutation-a-1-ldots-a-n-of-the-vertices-v-1-ldots%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 '18 at 20:05
Start with a base case where you have 2 vertices, show that it works, use induction over the number of vertices.
– B.Swan
Nov 20 '18 at 20:19
1
Furthermore, there is a unique permutation $(A_1,A_2,ldots,A_n)$ such that $(A_1,A_2,ldots,A_n)$ forms a directed path in $G$ iff $G$ has no directed cycles (i.e., a closed path $(v_1,v_2,ldots,v_l,v_1)$, where each $v_{i}v_{i+1}$ is an arc in $G$ for $i=1,2,ldots,l-1$, and $v_lv_1$ is also an arc in $G$). Equivalently, there exists a permutation $(A_1,A_2,dots,A_n)$ of vertices such that the in-degree of $A_i$ is $i-1$ for each $i=1,2,dots,n$. Equivalently, the relation $to$ on $V$ defined by $$uto v$$ iff there is a directed path in $G$ from $u$ to $v$ is an order relation on $V$.
– Batominovski
Nov 20 '18 at 21:04