There exists a permutation $(A_1, ldots , A_n)$ of the vertices $V ={1,ldots,n}$ such that for all...
up vote
1
down vote
favorite
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 at 20:48
Batominovski
31.6k23188
asked Nov 20 at 19:58
yorkliang
61
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
favorite
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 at 20:48
Batominovski
31.6k23188
asked Nov 20 at 19:58
yorkliang
61
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 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 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 at 21:04
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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 at 20:48
Batominovski
31.6k23188
asked Nov 20 at 19:58
yorkliang
61
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 at 20:48
Batominovski
31.6k23188
asked Nov 20 at 19:58
yorkliang
61
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Nov 20 at 20:48
Batominovski
31.6k23188
asked Nov 20 at 19:58
yorkliang
61
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Nov 20 at 20:48
Batominovski
31.6k23188
edited Nov 20 at 20:48
Batominovski
31.6k23188
edited Nov 20 at 20:48
Batominovski
31.6k23188
31.6k23188
asked Nov 20 at 19:58
yorkliang
61
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 20 at 19:58
yorkliang
61
asked Nov 20 at 19:58
yorkliang
61
61
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
yorkliang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Where did you get stuck? If you show your thought process so far, we can better help you.
– Santana Afton
Nov 20 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 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 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 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 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 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 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 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 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 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 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 at 21:04
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
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 at 20:53
Batominovski
31.6k23188
answered Nov 20 at 20:21
mathnoob
92813
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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 at 20:53
Batominovski
31.6k23188
answered Nov 20 at 20:21
mathnoob
92813
add a comment |
up vote
1
down vote
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 at 20:53
Batominovski
31.6k23188
answered Nov 20 at 20:21
mathnoob
92813
add a comment |
up vote
1
down vote
up vote
1
down vote
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 at 20:53
Batominovski
31.6k23188
answered Nov 20 at 20:21
mathnoob
92813
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 at 20:53
Batominovski
31.6k23188
answered Nov 20 at 20:21
mathnoob
92813
edited Nov 20 at 20:53
Batominovski
31.6k23188
edited Nov 20 at 20:53
Batominovski
31.6k23188
edited Nov 20 at 20:53
Batominovski
31.6k23188
31.6k23188
answered Nov 20 at 20:21
mathnoob
92813
answered Nov 20 at 20:21
mathnoob
92813
answered Nov 20 at 20:21
mathnoob
92813
92813
add a comment |
add a comment |
yorkliang is a new contributor. Be nice, and check out our Code of Conduct.
yorkliang is a new contributor. Be nice, and check out our Code of Conduct.
yorkliang is a new contributor. Be nice, and check out our Code of Conduct.
yorkliang is a new contributor. Be nice, and check out our Code of Conduct.
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 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 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 at 21:04