Finding paths in a graph with n vertices
$begingroup$
Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where
V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1})
For paths, it's a sequence of (non-repeating) vertices.
For cycles, we only distinguish them if they form different subgraphs.
How many paths of length 2 are there in G?
How many paths of length 3 are there in G?
How many cycles are there in G?
I can obviously draw out the first couple cases and count this, but there has to be a summation formula or something I'm missing...
discrete-mathematics graph-theory
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
$endgroup$
add a comment |
$begingroup$
Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where
V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1})
For paths, it's a sequence of (non-repeating) vertices.
For cycles, we only distinguish them if they form different subgraphs.
How many paths of length 2 are there in G?
How many paths of length 3 are there in G?
How many cycles are there in G?
I can obviously draw out the first couple cases and count this, but there has to be a summation formula or something I'm missing...
discrete-mathematics graph-theory
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
$endgroup$
$begingroup$
If $d_0,d_1,dots,d_n$ is the degree sequence, then the number of paths of length $2$ (paths with $2$ edges, $3$ vertices) is $$sum_{i=0}^nbinom{d_i}2 = binom n2+nbinom32=frac{n(n+5)}2$$
$endgroup$
– bof
Feb 8 '17 at 12:57
$begingroup$
The number of cycles is $$1+2binom n2=n^2-n+1$$
$endgroup$
– bof
Feb 8 '17 at 13:05
add a comment |
$begingroup$
Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where
V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1})
For paths, it's a sequence of (non-repeating) vertices.
For cycles, we only distinguish them if they form different subgraphs.
How many paths of length 2 are there in G?
How many paths of length 3 are there in G?
How many cycles are there in G?
I can obviously draw out the first couple cases and count this, but there has to be a summation formula or something I'm missing...
discrete-mathematics graph-theory
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
$endgroup$
Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where
V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1})
For paths, it's a sequence of (non-repeating) vertices.
For cycles, we only distinguish them if they form different subgraphs.
How many paths of length 2 are there in G?
How many paths of length 3 are there in G?
How many cycles are there in G?
I can obviously draw out the first couple cases and count this, but there has to be a summation formula or something I'm missing...
discrete-mathematics graph-theory
discrete-mathematics graph-theory
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
asked Apr 3 '14 at 2:41
ConfusedGraphTheoristConfusedGraphTheorist
11
11
$begingroup$
If $d_0,d_1,dots,d_n$ is the degree sequence, then the number of paths of length $2$ (paths with $2$ edges, $3$ vertices) is $$sum_{i=0}^nbinom{d_i}2 = binom n2+nbinom32=frac{n(n+5)}2$$
$endgroup$
– bof
Feb 8 '17 at 12:57
$begingroup$
The number of cycles is $$1+2binom n2=n^2-n+1$$
$endgroup$
– bof
Feb 8 '17 at 13:05
add a comment |
$begingroup$
If $d_0,d_1,dots,d_n$ is the degree sequence, then the number of paths of length $2$ (paths with $2$ edges, $3$ vertices) is $$sum_{i=0}^nbinom{d_i}2 = binom n2+nbinom32=frac{n(n+5)}2$$
$endgroup$
– bof
Feb 8 '17 at 12:57
$begingroup$
The number of cycles is $$1+2binom n2=n^2-n+1$$
$endgroup$
– bof
Feb 8 '17 at 13:05
$begingroup$
If $d_0,d_1,dots,d_n$ is the degree sequence, then the number of paths of length $2$ (paths with $2$ edges, $3$ vertices) is $$sum_{i=0}^nbinom{d_i}2 = binom n2+nbinom32=frac{n(n+5)}2$$
$endgroup$
– bof
Feb 8 '17 at 12:57
$begingroup$
If $d_0,d_1,dots,d_n$ is the degree sequence, then the number of paths of length $2$ (paths with $2$ edges, $3$ vertices) is $$sum_{i=0}^nbinom{d_i}2 = binom n2+nbinom32=frac{n(n+5)}2$$
$endgroup$
– bof
Feb 8 '17 at 12:57
$begingroup$
The number of cycles is $$1+2binom n2=n^2-n+1$$
$endgroup$
– bof
Feb 8 '17 at 13:05
$begingroup$
The number of cycles is $$1+2binom n2=n^2-n+1$$
$endgroup$
– bof
Feb 8 '17 at 13:05
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Assume that $nge4$: smaller cases are sometimes a bit different and can be investigated individually.
Paths of length $2$ are just (directed) edges: there are $2n$ edges and allowing for the direction gives $4n$ paths.
For paths of length $3$
- without the centre vertex, choose the first vertex and the "direction of travel": $2n$ possibilities;
- starting with the centre vertex, choose the second vertex and one of its two neighbours: $2n$ possibilities;
- ending with the centre vertex: same as the previous case;
- with the centre vertex in the middle, choose the first and last vertex: they must not be the same: $n(n-1)$ possibilities.
So the total number is $n^2+5n$.
Since $nge4$, a cycle of length $3$ can only consist of two adjacent vertices on the "circumference", together with the centre: to look at it another way, one of the edges on the "circumference" together with the two edges joining it to the centre. There are $n$ possibilities.
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
$endgroup$
add a comment |
$begingroup$
The graph you are describing is a Wheel graph: http://en.wikipedia.org/wiki/Wheel_graph
To get the number of $P_{3}$ (a path of length $2$, which has $3$ vertices) in the graph, you consider the paths along the exterior of the graph. There are $n$ such paths, where $n = |V|$. Then you look at the interior paths (only interior edges are used) through the center vertex, which forms an arithmetic progression $sum_{i=1}^{n-1} i$. Finally, you count paths using an exterior and an interior edge. You again get $n$ such paths.
To count cycles, you have $C_{i}$, for $i in {3, ..., n}$, for $n geq 3$.
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
$endgroup$
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%2f737556%2ffinding-paths-in-a-graph-with-n-vertices%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$
Assume that $nge4$: smaller cases are sometimes a bit different and can be investigated individually.
Paths of length $2$ are just (directed) edges: there are $2n$ edges and allowing for the direction gives $4n$ paths.
For paths of length $3$
- without the centre vertex, choose the first vertex and the "direction of travel": $2n$ possibilities;
- starting with the centre vertex, choose the second vertex and one of its two neighbours: $2n$ possibilities;
- ending with the centre vertex: same as the previous case;
- with the centre vertex in the middle, choose the first and last vertex: they must not be the same: $n(n-1)$ possibilities.
So the total number is $n^2+5n$.
Since $nge4$, a cycle of length $3$ can only consist of two adjacent vertices on the "circumference", together with the centre: to look at it another way, one of the edges on the "circumference" together with the two edges joining it to the centre. There are $n$ possibilities.
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
$endgroup$
add a comment |
$begingroup$
Assume that $nge4$: smaller cases are sometimes a bit different and can be investigated individually.
Paths of length $2$ are just (directed) edges: there are $2n$ edges and allowing for the direction gives $4n$ paths.
For paths of length $3$
- without the centre vertex, choose the first vertex and the "direction of travel": $2n$ possibilities;
- starting with the centre vertex, choose the second vertex and one of its two neighbours: $2n$ possibilities;
- ending with the centre vertex: same as the previous case;
- with the centre vertex in the middle, choose the first and last vertex: they must not be the same: $n(n-1)$ possibilities.
So the total number is $n^2+5n$.
Since $nge4$, a cycle of length $3$ can only consist of two adjacent vertices on the "circumference", together with the centre: to look at it another way, one of the edges on the "circumference" together with the two edges joining it to the centre. There are $n$ possibilities.
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
$endgroup$
add a comment |
$begingroup$
Assume that $nge4$: smaller cases are sometimes a bit different and can be investigated individually.
Paths of length $2$ are just (directed) edges: there are $2n$ edges and allowing for the direction gives $4n$ paths.
For paths of length $3$
- without the centre vertex, choose the first vertex and the "direction of travel": $2n$ possibilities;
- starting with the centre vertex, choose the second vertex and one of its two neighbours: $2n$ possibilities;
- ending with the centre vertex: same as the previous case;
- with the centre vertex in the middle, choose the first and last vertex: they must not be the same: $n(n-1)$ possibilities.
So the total number is $n^2+5n$.
Since $nge4$, a cycle of length $3$ can only consist of two adjacent vertices on the "circumference", together with the centre: to look at it another way, one of the edges on the "circumference" together with the two edges joining it to the centre. There are $n$ possibilities.
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
$endgroup$
Assume that $nge4$: smaller cases are sometimes a bit different and can be investigated individually.
Paths of length $2$ are just (directed) edges: there are $2n$ edges and allowing for the direction gives $4n$ paths.
For paths of length $3$
- without the centre vertex, choose the first vertex and the "direction of travel": $2n$ possibilities;
- starting with the centre vertex, choose the second vertex and one of its two neighbours: $2n$ possibilities;
- ending with the centre vertex: same as the previous case;
- with the centre vertex in the middle, choose the first and last vertex: they must not be the same: $n(n-1)$ possibilities.
So the total number is $n^2+5n$.
Since $nge4$, a cycle of length $3$ can only consist of two adjacent vertices on the "circumference", together with the centre: to look at it another way, one of the edges on the "circumference" together with the two edges joining it to the centre. There are $n$ possibilities.
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
answered Apr 3 '14 at 4:08
DavidDavid
67.8k664126
67.8k664126
add a comment |
add a comment |
$begingroup$
The graph you are describing is a Wheel graph: http://en.wikipedia.org/wiki/Wheel_graph
To get the number of $P_{3}$ (a path of length $2$, which has $3$ vertices) in the graph, you consider the paths along the exterior of the graph. There are $n$ such paths, where $n = |V|$. Then you look at the interior paths (only interior edges are used) through the center vertex, which forms an arithmetic progression $sum_{i=1}^{n-1} i$. Finally, you count paths using an exterior and an interior edge. You again get $n$ such paths.
To count cycles, you have $C_{i}$, for $i in {3, ..., n}$, for $n geq 3$.
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
$endgroup$
add a comment |
$begingroup$
The graph you are describing is a Wheel graph: http://en.wikipedia.org/wiki/Wheel_graph
To get the number of $P_{3}$ (a path of length $2$, which has $3$ vertices) in the graph, you consider the paths along the exterior of the graph. There are $n$ such paths, where $n = |V|$. Then you look at the interior paths (only interior edges are used) through the center vertex, which forms an arithmetic progression $sum_{i=1}^{n-1} i$. Finally, you count paths using an exterior and an interior edge. You again get $n$ such paths.
To count cycles, you have $C_{i}$, for $i in {3, ..., n}$, for $n geq 3$.
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
$endgroup$
add a comment |
$begingroup$
The graph you are describing is a Wheel graph: http://en.wikipedia.org/wiki/Wheel_graph
To get the number of $P_{3}$ (a path of length $2$, which has $3$ vertices) in the graph, you consider the paths along the exterior of the graph. There are $n$ such paths, where $n = |V|$. Then you look at the interior paths (only interior edges are used) through the center vertex, which forms an arithmetic progression $sum_{i=1}^{n-1} i$. Finally, you count paths using an exterior and an interior edge. You again get $n$ such paths.
To count cycles, you have $C_{i}$, for $i in {3, ..., n}$, for $n geq 3$.
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
$endgroup$
The graph you are describing is a Wheel graph: http://en.wikipedia.org/wiki/Wheel_graph
To get the number of $P_{3}$ (a path of length $2$, which has $3$ vertices) in the graph, you consider the paths along the exterior of the graph. There are $n$ such paths, where $n = |V|$. Then you look at the interior paths (only interior edges are used) through the center vertex, which forms an arithmetic progression $sum_{i=1}^{n-1} i$. Finally, you count paths using an exterior and an interior edge. You again get $n$ such paths.
To count cycles, you have $C_{i}$, for $i in {3, ..., n}$, for $n geq 3$.
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
edited Apr 3 '14 at 4:14
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
answered Apr 3 '14 at 3:15
ml0105ml0105
11.4k21538
11.4k21538
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.
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%2f737556%2ffinding-paths-in-a-graph-with-n-vertices%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
$begingroup$
If $d_0,d_1,dots,d_n$ is the degree sequence, then the number of paths of length $2$ (paths with $2$ edges, $3$ vertices) is $$sum_{i=0}^nbinom{d_i}2 = binom n2+nbinom32=frac{n(n+5)}2$$
$endgroup$
– bof
Feb 8 '17 at 12:57
$begingroup$
The number of cycles is $$1+2binom n2=n^2-n+1$$
$endgroup$
– bof
Feb 8 '17 at 13:05