Can there be a repeated edge in a path?
$begingroup$
I was just brushing up on my discrete mathematics specifically graph theory and read the following definition of a walk in a graph
"A walk in a graph is an alternating sequence of vertices and edges from a start vertex to an end vertex where start and the end vertices are not necessarily distinct"
and after this I read up the definition of a path in a graph which says
"A path in a graph is a walk in the graph with no repeated vertices"
the point of confusion is that the definition for a path doesn't mention anything about the repetition of edges in a path, although the idea of repetition of edge in a path sounds absurd to me because that eventually means that I am taking the same road that I traversed previously and hence repeating the same destinations which are the vertices respectively. I am curious to know if there is any such case of a path where there is a repetitive edge but no repeated vertex.
One more thing I would like to know is can there exists an ordering of edges in a graph such that the path from one vertex to another is infinite in short can there be an infinite path in a finite graph?
discrete-mathematics graph-theory
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
$endgroup$
add a comment |
$begingroup$
I was just brushing up on my discrete mathematics specifically graph theory and read the following definition of a walk in a graph
"A walk in a graph is an alternating sequence of vertices and edges from a start vertex to an end vertex where start and the end vertices are not necessarily distinct"
and after this I read up the definition of a path in a graph which says
"A path in a graph is a walk in the graph with no repeated vertices"
the point of confusion is that the definition for a path doesn't mention anything about the repetition of edges in a path, although the idea of repetition of edge in a path sounds absurd to me because that eventually means that I am taking the same road that I traversed previously and hence repeating the same destinations which are the vertices respectively. I am curious to know if there is any such case of a path where there is a repetitive edge but no repeated vertex.
One more thing I would like to know is can there exists an ordering of edges in a graph such that the path from one vertex to another is infinite in short can there be an infinite path in a finite graph?
discrete-mathematics graph-theory
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
$endgroup$
add a comment |
$begingroup$
I was just brushing up on my discrete mathematics specifically graph theory and read the following definition of a walk in a graph
"A walk in a graph is an alternating sequence of vertices and edges from a start vertex to an end vertex where start and the end vertices are not necessarily distinct"
and after this I read up the definition of a path in a graph which says
"A path in a graph is a walk in the graph with no repeated vertices"
the point of confusion is that the definition for a path doesn't mention anything about the repetition of edges in a path, although the idea of repetition of edge in a path sounds absurd to me because that eventually means that I am taking the same road that I traversed previously and hence repeating the same destinations which are the vertices respectively. I am curious to know if there is any such case of a path where there is a repetitive edge but no repeated vertex.
One more thing I would like to know is can there exists an ordering of edges in a graph such that the path from one vertex to another is infinite in short can there be an infinite path in a finite graph?
discrete-mathematics graph-theory
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
$endgroup$
I was just brushing up on my discrete mathematics specifically graph theory and read the following definition of a walk in a graph
"A walk in a graph is an alternating sequence of vertices and edges from a start vertex to an end vertex where start and the end vertices are not necessarily distinct"
and after this I read up the definition of a path in a graph which says
"A path in a graph is a walk in the graph with no repeated vertices"
the point of confusion is that the definition for a path doesn't mention anything about the repetition of edges in a path, although the idea of repetition of edge in a path sounds absurd to me because that eventually means that I am taking the same road that I traversed previously and hence repeating the same destinations which are the vertices respectively. I am curious to know if there is any such case of a path where there is a repetitive edge but no repeated vertex.
One more thing I would like to know is can there exists an ordering of edges in a graph such that the path from one vertex to another is infinite in short can there be an infinite path in a finite graph?
discrete-mathematics graph-theory
discrete-mathematics graph-theory
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
edited Jan 13 at 4:20
Misha Lavrov
47.5k657107
47.5k657107
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
asked Jun 10 '13 at 10:24
AnkitSablokAnkitSablok
3051820
3051820
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The terminology varies a bit from textbook to textbook, so it's always a good idea to check the conventions used by that particular author.
I assume that the definitions you work with are the ones you state. Then there can not be a repeated edge in a path. If an edge occurs twice in the same path, then both of its endpoints would also occur twice among the visited vertices.
For the second question, a finite graph has a finite number of edges and a finite number of vertices, so as long as no repetition are allowed, a path would have to be finitely long.
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
$endgroup$
1
$begingroup$
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated
$endgroup$
– AnkitSablok
Jun 10 '13 at 13:02
add a comment |
$begingroup$
walk - in walk what happened tha we can not visit the one single visit the single edges more than one time while walking ya but we can visit the single virtices more than one time
path - already we know that in path we cant visit the single virtices more than one time think a bit how we can visit the any edges more than one time if we are not able to visit the same virtices more than one time .
answered Jan 12 at 6:46
user633968user633968
1
$endgroup$
1
$begingroup$
This is very hard to understand. Have a look at other accepted answers on the site and see how they are written for examples, and try revising this.
$endgroup$
– postmortes
Jan 12 at 7:03
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%2f416291%2fcan-there-be-a-repeated-edge-in-a-path%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The terminology varies a bit from textbook to textbook, so it's always a good idea to check the conventions used by that particular author.
I assume that the definitions you work with are the ones you state. Then there can not be a repeated edge in a path. If an edge occurs twice in the same path, then both of its endpoints would also occur twice among the visited vertices.
For the second question, a finite graph has a finite number of edges and a finite number of vertices, so as long as no repetition are allowed, a path would have to be finitely long.
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
$endgroup$
1
$begingroup$
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated
$endgroup$
– AnkitSablok
Jun 10 '13 at 13:02
add a comment |
$begingroup$
The terminology varies a bit from textbook to textbook, so it's always a good idea to check the conventions used by that particular author.
I assume that the definitions you work with are the ones you state. Then there can not be a repeated edge in a path. If an edge occurs twice in the same path, then both of its endpoints would also occur twice among the visited vertices.
For the second question, a finite graph has a finite number of edges and a finite number of vertices, so as long as no repetition are allowed, a path would have to be finitely long.
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
$endgroup$
1
$begingroup$
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated
$endgroup$
– AnkitSablok
Jun 10 '13 at 13:02
add a comment |
$begingroup$
The terminology varies a bit from textbook to textbook, so it's always a good idea to check the conventions used by that particular author.
I assume that the definitions you work with are the ones you state. Then there can not be a repeated edge in a path. If an edge occurs twice in the same path, then both of its endpoints would also occur twice among the visited vertices.
For the second question, a finite graph has a finite number of edges and a finite number of vertices, so as long as no repetition are allowed, a path would have to be finitely long.
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
$endgroup$
The terminology varies a bit from textbook to textbook, so it's always a good idea to check the conventions used by that particular author.
I assume that the definitions you work with are the ones you state. Then there can not be a repeated edge in a path. If an edge occurs twice in the same path, then both of its endpoints would also occur twice among the visited vertices.
For the second question, a finite graph has a finite number of edges and a finite number of vertices, so as long as no repetition are allowed, a path would have to be finitely long.
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
edited Jun 10 '13 at 11:10
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
answered Jun 10 '13 at 10:42
mrfmrf
37.6k64786
37.6k64786
1
$begingroup$
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated
$endgroup$
– AnkitSablok
Jun 10 '13 at 13:02
add a comment |
1
$begingroup$
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated
$endgroup$
– AnkitSablok
Jun 10 '13 at 13:02
1
1
$begingroup$
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated
$endgroup$
– AnkitSablok
Jun 10 '13 at 13:02
$begingroup$
The thing is a walk can have repeated vertices and edges but a path is a special type of walk where no vertex is repeated
$endgroup$
– AnkitSablok
Jun 10 '13 at 13:02
add a comment |
$begingroup$
walk - in walk what happened tha we can not visit the one single visit the single edges more than one time while walking ya but we can visit the single virtices more than one time
path - already we know that in path we cant visit the single virtices more than one time think a bit how we can visit the any edges more than one time if we are not able to visit the same virtices more than one time .
answered Jan 12 at 6:46
user633968user633968
1
$endgroup$
1
$begingroup$
This is very hard to understand. Have a look at other accepted answers on the site and see how they are written for examples, and try revising this.
$endgroup$
– postmortes
Jan 12 at 7:03
add a comment |
$begingroup$
walk - in walk what happened tha we can not visit the one single visit the single edges more than one time while walking ya but we can visit the single virtices more than one time
path - already we know that in path we cant visit the single virtices more than one time think a bit how we can visit the any edges more than one time if we are not able to visit the same virtices more than one time .
answered Jan 12 at 6:46
user633968user633968
1
$endgroup$
1
$begingroup$
This is very hard to understand. Have a look at other accepted answers on the site and see how they are written for examples, and try revising this.
$endgroup$
– postmortes
Jan 12 at 7:03
add a comment |
$begingroup$
walk - in walk what happened tha we can not visit the one single visit the single edges more than one time while walking ya but we can visit the single virtices more than one time
path - already we know that in path we cant visit the single virtices more than one time think a bit how we can visit the any edges more than one time if we are not able to visit the same virtices more than one time .
answered Jan 12 at 6:46
user633968user633968
1
$endgroup$
walk - in walk what happened tha we can not visit the one single visit the single edges more than one time while walking ya but we can visit the single virtices more than one time
path - already we know that in path we cant visit the single virtices more than one time think a bit how we can visit the any edges more than one time if we are not able to visit the same virtices more than one time .
answered Jan 12 at 6:46
user633968user633968
1
answered Jan 12 at 6:46
user633968user633968
1
answered Jan 12 at 6:46
user633968user633968
1
answered Jan 12 at 6:46
user633968user633968
1
1
1
$begingroup$
This is very hard to understand. Have a look at other accepted answers on the site and see how they are written for examples, and try revising this.
$endgroup$
– postmortes
Jan 12 at 7:03
add a comment |
1
$begingroup$
This is very hard to understand. Have a look at other accepted answers on the site and see how they are written for examples, and try revising this.
$endgroup$
– postmortes
Jan 12 at 7:03
1
1
$begingroup$
This is very hard to understand. Have a look at other accepted answers on the site and see how they are written for examples, and try revising this.
$endgroup$
– postmortes
Jan 12 at 7:03
$begingroup$
This is very hard to understand. Have a look at other accepted answers on the site and see how they are written for examples, and try revising this.
$endgroup$
– postmortes
Jan 12 at 7:03
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.
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%2f416291%2fcan-there-be-a-repeated-edge-in-a-path%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
