How to prove that a connected graph with $|V| -1= |E|$ is a tree?
$begingroup$
I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree.
Could somebody please provide an argument to establish this.
combinatorics graph-theory trees
edited Nov 22 '15 at 20:11
quid♦
37k95093
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
$endgroup$
add a comment |
$begingroup$
I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree.
Could somebody please provide an argument to establish this.
combinatorics graph-theory trees
edited Nov 22 '15 at 20:11
quid♦
37k95093
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
$endgroup$
add a comment |
$begingroup$
I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree.
Could somebody please provide an argument to establish this.
combinatorics graph-theory trees
edited Nov 22 '15 at 20:11
quid♦
37k95093
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
$endgroup$
I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree.
Could somebody please provide an argument to establish this.
combinatorics graph-theory trees
combinatorics graph-theory trees
edited Nov 22 '15 at 20:11
quid♦
37k95093
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
edited Nov 22 '15 at 20:11
quid♦
37k95093
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
edited Nov 22 '15 at 20:11
quid♦
37k95093
edited Nov 22 '15 at 20:11
quid♦
37k95093
edited Nov 22 '15 at 20:11
quid♦
37k95093
37k95093
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
asked Nov 22 '15 at 19:47
Serkan KlvzSerkan Klvz
316
316
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges).
Suppose a connected graph on $n$ vertices has $n-1$ edges, we must prove no cycle exists, suppose it does, if we remove an edge from the cycle we get a connected graph (because if we have a path that uses this edge, instead of using the edge we can go around the remaining part of the cycle). This is a contradiction, since the graph would have $n-2$ edges, and would hence not be connected.
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
$endgroup$
add a comment |
$begingroup$
Suppose $|V| ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$.
Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph itself.
Using this starting idea you can set up a proof by induction.
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
$endgroup$
add a comment |
$begingroup$
Suppose the graph contains cycles, then we can remove an edge without removing a vertex and the graph is still connected. After removing, it will has $n$ vertices and $n - 2$ edges. Continue to do so until we reach a tree (because there is no cycle) with $n$ vertices and $n - k$ edges $(k > 1)$. However it contradicts with the fact that a tree with $n$ vertices must has $n - 1$ edges.
Therefore the graph must not contain cycles, and then it is a tree by definition.
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
$endgroup$
$begingroup$
Welcome to MSE! Please format questions and answers using MathJax for mathematical notation. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– platty
Nov 30 '18 at 2:33
$begingroup$
@platty: Thank you for informing. I have already fixed my mathematical notations.
$endgroup$
– Quan Nguyen
Dec 4 '18 at 10:01
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%2f1541624%2fhow-to-prove-that-a-connected-graph-with-v-1-e-is-a-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges).
Suppose a connected graph on $n$ vertices has $n-1$ edges, we must prove no cycle exists, suppose it does, if we remove an edge from the cycle we get a connected graph (because if we have a path that uses this edge, instead of using the edge we can go around the remaining part of the cycle). This is a contradiction, since the graph would have $n-2$ edges, and would hence not be connected.
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
$endgroup$
add a comment |
$begingroup$
An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges).
Suppose a connected graph on $n$ vertices has $n-1$ edges, we must prove no cycle exists, suppose it does, if we remove an edge from the cycle we get a connected graph (because if we have a path that uses this edge, instead of using the edge we can go around the remaining part of the cycle). This is a contradiction, since the graph would have $n-2$ edges, and would hence not be connected.
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
$endgroup$
add a comment |
$begingroup$
An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges).
Suppose a connected graph on $n$ vertices has $n-1$ edges, we must prove no cycle exists, suppose it does, if we remove an edge from the cycle we get a connected graph (because if we have a path that uses this edge, instead of using the edge we can go around the remaining part of the cycle). This is a contradiction, since the graph would have $n-2$ edges, and would hence not be connected.
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
$endgroup$
An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges).
Suppose a connected graph on $n$ vertices has $n-1$ edges, we must prove no cycle exists, suppose it does, if we remove an edge from the cycle we get a connected graph (because if we have a path that uses this edge, instead of using the edge we can go around the remaining part of the cycle). This is a contradiction, since the graph would have $n-2$ edges, and would hence not be connected.
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
answered Nov 22 '15 at 21:17
Jorge FernándezJorge Fernández
75.2k1190192
75.2k1190192
add a comment |
add a comment |
$begingroup$
Suppose $|V| ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$.
Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph itself.
Using this starting idea you can set up a proof by induction.
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
$endgroup$
add a comment |
$begingroup$
Suppose $|V| ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$.
Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph itself.
Using this starting idea you can set up a proof by induction.
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
$endgroup$
add a comment |
$begingroup$
Suppose $|V| ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$.
Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph itself.
Using this starting idea you can set up a proof by induction.
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
$endgroup$
Suppose $|V| ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$.
Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph itself.
Using this starting idea you can set up a proof by induction.
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
answered Nov 22 '15 at 20:08
quid♦quid
37k95093
37k95093
add a comment |
add a comment |
$begingroup$
Suppose the graph contains cycles, then we can remove an edge without removing a vertex and the graph is still connected. After removing, it will has $n$ vertices and $n - 2$ edges. Continue to do so until we reach a tree (because there is no cycle) with $n$ vertices and $n - k$ edges $(k > 1)$. However it contradicts with the fact that a tree with $n$ vertices must has $n - 1$ edges.
Therefore the graph must not contain cycles, and then it is a tree by definition.
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
$endgroup$
$begingroup$
Welcome to MSE! Please format questions and answers using MathJax for mathematical notation. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– platty
Nov 30 '18 at 2:33
$begingroup$
@platty: Thank you for informing. I have already fixed my mathematical notations.
$endgroup$
– Quan Nguyen
Dec 4 '18 at 10:01
add a comment |
$begingroup$
Suppose the graph contains cycles, then we can remove an edge without removing a vertex and the graph is still connected. After removing, it will has $n$ vertices and $n - 2$ edges. Continue to do so until we reach a tree (because there is no cycle) with $n$ vertices and $n - k$ edges $(k > 1)$. However it contradicts with the fact that a tree with $n$ vertices must has $n - 1$ edges.
Therefore the graph must not contain cycles, and then it is a tree by definition.
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
$endgroup$
$begingroup$
Welcome to MSE! Please format questions and answers using MathJax for mathematical notation. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– platty
Nov 30 '18 at 2:33
$begingroup$
@platty: Thank you for informing. I have already fixed my mathematical notations.
$endgroup$
– Quan Nguyen
Dec 4 '18 at 10:01
add a comment |
$begingroup$
Suppose the graph contains cycles, then we can remove an edge without removing a vertex and the graph is still connected. After removing, it will has $n$ vertices and $n - 2$ edges. Continue to do so until we reach a tree (because there is no cycle) with $n$ vertices and $n - k$ edges $(k > 1)$. However it contradicts with the fact that a tree with $n$ vertices must has $n - 1$ edges.
Therefore the graph must not contain cycles, and then it is a tree by definition.
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
$endgroup$
Suppose the graph contains cycles, then we can remove an edge without removing a vertex and the graph is still connected. After removing, it will has $n$ vertices and $n - 2$ edges. Continue to do so until we reach a tree (because there is no cycle) with $n$ vertices and $n - k$ edges $(k > 1)$. However it contradicts with the fact that a tree with $n$ vertices must has $n - 1$ edges.
Therefore the graph must not contain cycles, and then it is a tree by definition.
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
edited Dec 4 '18 at 10:00
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
answered Nov 30 '18 at 1:52
Quan NguyenQuan Nguyen
11
11
$begingroup$
Welcome to MSE! Please format questions and answers using MathJax for mathematical notation. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– platty
Nov 30 '18 at 2:33
$begingroup$
@platty: Thank you for informing. I have already fixed my mathematical notations.
$endgroup$
– Quan Nguyen
Dec 4 '18 at 10:01
add a comment |
$begingroup$
Welcome to MSE! Please format questions and answers using MathJax for mathematical notation. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– platty
Nov 30 '18 at 2:33
$begingroup$
@platty: Thank you for informing. I have already fixed my mathematical notations.
$endgroup$
– Quan Nguyen
Dec 4 '18 at 10:01
$begingroup$
Welcome to MSE! Please format questions and answers using MathJax for mathematical notation. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– platty
Nov 30 '18 at 2:33
$begingroup$
Welcome to MSE! Please format questions and answers using MathJax for mathematical notation. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– platty
Nov 30 '18 at 2:33
$begingroup$
@platty: Thank you for informing. I have already fixed my mathematical notations.
$endgroup$
– Quan Nguyen
Dec 4 '18 at 10:01
$begingroup$
@platty: Thank you for informing. I have already fixed my mathematical notations.
$endgroup$
– Quan Nguyen
Dec 4 '18 at 10:01
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%2f1541624%2fhow-to-prove-that-a-connected-graph-with-v-1-e-is-a-tree%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
