Minimum number of cycles of a graph with $n$ vertices, $m$ edges and $c$ components.
Let $G$ be a graph with $n$ vertices, $m$ edges and $c$ components. Prove that $G$ contains at least $m-n+c$ cycles.
My Professor just forwards this question during lecture time but I don't have enough information how to tackle the proof of this statement. Any help is appreciated.
graph-theory
asked Nov 25 '18 at 9:38
2468
505
add a comment |
Let $G$ be a graph with $n$ vertices, $m$ edges and $c$ components. Prove that $G$ contains at least $m-n+c$ cycles.
My Professor just forwards this question during lecture time but I don't have enough information how to tackle the proof of this statement. Any help is appreciated.
graph-theory
asked Nov 25 '18 at 9:38
2468
505
What if $c$ is 1. What do you know for that case?
– Mike
Nov 25 '18 at 11:32
I read that it is $m-n+1$ but I don't know how it came.
– 2468
Nov 25 '18 at 16:46
This post has an elegant solution!!! math.stackexchange.com/questions/225570/… Take a look!
– mathnoob
Nov 29 '18 at 19:30
add a comment |
Let $G$ be a graph with $n$ vertices, $m$ edges and $c$ components. Prove that $G$ contains at least $m-n+c$ cycles.
My Professor just forwards this question during lecture time but I don't have enough information how to tackle the proof of this statement. Any help is appreciated.
graph-theory
asked Nov 25 '18 at 9:38
2468
505
Let $G$ be a graph with $n$ vertices, $m$ edges and $c$ components. Prove that $G$ contains at least $m-n+c$ cycles.
My Professor just forwards this question during lecture time but I don't have enough information how to tackle the proof of this statement. Any help is appreciated.
graph-theory
graph-theory
asked Nov 25 '18 at 9:38
2468
505
asked Nov 25 '18 at 9:38
2468
505
edited Nov 25 '18 at 10:07
asked Nov 25 '18 at 9:38
2468
505
asked Nov 25 '18 at 9:38
2468
505
asked Nov 25 '18 at 9:38
2468
505
505
What if $c$ is 1. What do you know for that case?
– Mike
Nov 25 '18 at 11:32
I read that it is $m-n+1$ but I don't know how it came.
– 2468
Nov 25 '18 at 16:46
This post has an elegant solution!!! math.stackexchange.com/questions/225570/… Take a look!
– mathnoob
Nov 29 '18 at 19:30
add a comment |
What if $c$ is 1. What do you know for that case?
– Mike
Nov 25 '18 at 11:32
I read that it is $m-n+1$ but I don't know how it came.
– 2468
Nov 25 '18 at 16:46
This post has an elegant solution!!! math.stackexchange.com/questions/225570/… Take a look!
– mathnoob
Nov 29 '18 at 19:30
What if $c$ is 1. What do you know for that case?
– Mike
Nov 25 '18 at 11:32
What if $c$ is 1. What do you know for that case?
– Mike
Nov 25 '18 at 11:32
I read that it is $m-n+1$ but I don't know how it came.
– 2468
Nov 25 '18 at 16:46
I read that it is $m-n+1$ but I don't know how it came.
– 2468
Nov 25 '18 at 16:46
This post has an elegant solution!!! math.stackexchange.com/questions/225570/… Take a look!
– mathnoob
Nov 29 '18 at 19:30
This post has an elegant solution!!! math.stackexchange.com/questions/225570/… Take a look!
– mathnoob
Nov 29 '18 at 19:30
add a comment |
1 Answer
1
active
oldest
votes
Number of components in a forest $G$ is $|V(G)|$-$|E(G)|$, now, we have $c$ components and $n$ vertices, so the number of edges in the spanning trees of the graph is $n-c$. Now we have the remaining $m-(n-c)$ edges that are not part of the spanning tree. Whenever you add one of those edges to the spanning tree, you get a cycle. So you get at least $m-n+c$ cycles.
answered Nov 29 '18 at 19:37
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%2f3012632%2fminimum-number-of-cycles-of-a-graph-with-n-vertices-m-edges-and-c-compone%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
Number of components in a forest $G$ is $|V(G)|$-$|E(G)|$, now, we have $c$ components and $n$ vertices, so the number of edges in the spanning trees of the graph is $n-c$. Now we have the remaining $m-(n-c)$ edges that are not part of the spanning tree. Whenever you add one of those edges to the spanning tree, you get a cycle. So you get at least $m-n+c$ cycles.
answered Nov 29 '18 at 19:37
mathnoob
1,799422
add a comment |
Number of components in a forest $G$ is $|V(G)|$-$|E(G)|$, now, we have $c$ components and $n$ vertices, so the number of edges in the spanning trees of the graph is $n-c$. Now we have the remaining $m-(n-c)$ edges that are not part of the spanning tree. Whenever you add one of those edges to the spanning tree, you get a cycle. So you get at least $m-n+c$ cycles.
answered Nov 29 '18 at 19:37
mathnoob
1,799422
add a comment |
Number of components in a forest $G$ is $|V(G)|$-$|E(G)|$, now, we have $c$ components and $n$ vertices, so the number of edges in the spanning trees of the graph is $n-c$. Now we have the remaining $m-(n-c)$ edges that are not part of the spanning tree. Whenever you add one of those edges to the spanning tree, you get a cycle. So you get at least $m-n+c$ cycles.
answered Nov 29 '18 at 19:37
mathnoob
1,799422
Number of components in a forest $G$ is $|V(G)|$-$|E(G)|$, now, we have $c$ components and $n$ vertices, so the number of edges in the spanning trees of the graph is $n-c$. Now we have the remaining $m-(n-c)$ edges that are not part of the spanning tree. Whenever you add one of those edges to the spanning tree, you get a cycle. So you get at least $m-n+c$ cycles.
answered Nov 29 '18 at 19:37
mathnoob
1,799422
answered Nov 29 '18 at 19:37
mathnoob
1,799422
answered Nov 29 '18 at 19:37
mathnoob
1,799422
answered Nov 29 '18 at 19:37
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%2f3012632%2fminimum-number-of-cycles-of-a-graph-with-n-vertices-m-edges-and-c-compone%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
What if $c$ is 1. What do you know for that case?
– Mike
Nov 25 '18 at 11:32
I read that it is $m-n+1$ but I don't know how it came.
– 2468
Nov 25 '18 at 16:46
This post has an elegant solution!!! math.stackexchange.com/questions/225570/… Take a look!
– mathnoob
Nov 29 '18 at 19:30