Mixing
Could a graph with $n>1$ vertices and $m<n-1$ edges be connected?
$begingroup$
It's easy to verify (with some n's) that's true but how can I formalize a proof to answer this question? Any hint?
discrete-mathematics graph-theory
edited Jan 27 at 16:24
David G. Stork
11.4k41433
asked Jan 27 at 16:16
JackJack
756
$endgroup$
add a comment |
$begingroup$
It's easy to verify (with some n's) that's true but how can I formalize a proof to answer this question? Any hint?
discrete-mathematics graph-theory
edited Jan 27 at 16:24
David G. Stork
11.4k41433
asked Jan 27 at 16:16
JackJack
756
$endgroup$
$begingroup$
A connected graph with $n$ vertices and $n-1$ edges is a tree. Or, consider the spanning tree of the graph.
$endgroup$
– saulspatz
Jan 27 at 16:18
$begingroup$
I had thought about this. In fact by removing a further edge (according to our hypotheses) the tree is no longer connected. But is it a good demonstration to use the example of the tree?
$endgroup$
– Jack
Jan 27 at 16:19
3
$begingroup$
Crossing comments. If the graph is connected, it has a spanning tree, but the spanning tree has $n-1$ edges, contradiction.
$endgroup$
– saulspatz
Jan 27 at 16:21
1
$begingroup$
In practice, though, we use this result to prove properties of trees (such as existence of spanning trees, and the number of edges in a tree) and not vice versa.
$endgroup$
– Misha Lavrov
Jan 27 at 17:02
$begingroup$
Hint: prove that a connected graph with n vertices has at least n−1 edges
$endgroup$
– W.R.P.S
Jan 27 at 21:17
add a comment |
$begingroup$
It's easy to verify (with some n's) that's true but how can I formalize a proof to answer this question? Any hint?
discrete-mathematics graph-theory
edited Jan 27 at 16:24
David G. Stork
11.4k41433
asked Jan 27 at 16:16
JackJack
756
$endgroup$
It's easy to verify (with some n's) that's true but how can I formalize a proof to answer this question? Any hint?
discrete-mathematics graph-theory
discrete-mathematics graph-theory
edited Jan 27 at 16:24
David G. Stork
11.4k41433
asked Jan 27 at 16:16
JackJack
756
edited Jan 27 at 16:24
David G. Stork
11.4k41433
asked Jan 27 at 16:16
JackJack
756
edited Jan 27 at 16:24
David G. Stork
11.4k41433
edited Jan 27 at 16:24
David G. Stork
11.4k41433
edited Jan 27 at 16:24
David G. Stork
11.4k41433
11.4k41433
asked Jan 27 at 16:16
JackJack
756
asked Jan 27 at 16:16
JackJack
756
asked Jan 27 at 16:16
JackJack
756
756
$begingroup$
A connected graph with $n$ vertices and $n-1$ edges is a tree. Or, consider the spanning tree of the graph.
$endgroup$
– saulspatz
Jan 27 at 16:18
$begingroup$
I had thought about this. In fact by removing a further edge (according to our hypotheses) the tree is no longer connected. But is it a good demonstration to use the example of the tree?
$endgroup$
– Jack
Jan 27 at 16:19
3
$begingroup$
Crossing comments. If the graph is connected, it has a spanning tree, but the spanning tree has $n-1$ edges, contradiction.
$endgroup$
– saulspatz
Jan 27 at 16:21
1
$begingroup$
In practice, though, we use this result to prove properties of trees (such as existence of spanning trees, and the number of edges in a tree) and not vice versa.
$endgroup$
– Misha Lavrov
Jan 27 at 17:02
$begingroup$
Hint: prove that a connected graph with n vertices has at least n−1 edges
$endgroup$
– W.R.P.S
Jan 27 at 21:17
add a comment |
$begingroup$
A connected graph with $n$ vertices and $n-1$ edges is a tree. Or, consider the spanning tree of the graph.
$endgroup$
– saulspatz
Jan 27 at 16:18
$begingroup$
I had thought about this. In fact by removing a further edge (according to our hypotheses) the tree is no longer connected. But is it a good demonstration to use the example of the tree?
$endgroup$
– Jack
Jan 27 at 16:19
3
$begingroup$
Crossing comments. If the graph is connected, it has a spanning tree, but the spanning tree has $n-1$ edges, contradiction.
$endgroup$
– saulspatz
Jan 27 at 16:21
1
$begingroup$
In practice, though, we use this result to prove properties of trees (such as existence of spanning trees, and the number of edges in a tree) and not vice versa.
$endgroup$
– Misha Lavrov
Jan 27 at 17:02
$begingroup$
Hint: prove that a connected graph with n vertices has at least n−1 edges
$endgroup$
– W.R.P.S
Jan 27 at 21:17
$begingroup$
A connected graph with $n$ vertices and $n-1$ edges is a tree. Or, consider the spanning tree of the graph.
$endgroup$
– saulspatz
Jan 27 at 16:18
$begingroup$
A connected graph with $n$ vertices and $n-1$ edges is a tree. Or, consider the spanning tree of the graph.
$endgroup$
– saulspatz
Jan 27 at 16:18
$begingroup$
I had thought about this. In fact by removing a further edge (according to our hypotheses) the tree is no longer connected. But is it a good demonstration to use the example of the tree?
$endgroup$
– Jack
Jan 27 at 16:19
$begingroup$
I had thought about this. In fact by removing a further edge (according to our hypotheses) the tree is no longer connected. But is it a good demonstration to use the example of the tree?
$endgroup$
– Jack
Jan 27 at 16:19
3
3
$begingroup$
Crossing comments. If the graph is connected, it has a spanning tree, but the spanning tree has $n-1$ edges, contradiction.
$endgroup$
– saulspatz
Jan 27 at 16:21
$begingroup$
Crossing comments. If the graph is connected, it has a spanning tree, but the spanning tree has $n-1$ edges, contradiction.
$endgroup$
– saulspatz
Jan 27 at 16:21
1
1
$begingroup$
In practice, though, we use this result to prove properties of trees (such as existence of spanning trees, and the number of edges in a tree) and not vice versa.
$endgroup$
– Misha Lavrov
Jan 27 at 17:02
$begingroup$
In practice, though, we use this result to prove properties of trees (such as existence of spanning trees, and the number of edges in a tree) and not vice versa.
$endgroup$
– Misha Lavrov
Jan 27 at 17:02
$begingroup$
Hint: prove that a connected graph with n vertices has at least n−1 edges
$endgroup$
– W.R.P.S
Jan 27 at 21:17
$begingroup$
Hint: prove that a connected graph with n vertices has at least n−1 edges
$endgroup$
– W.R.P.S
Jan 27 at 21:17
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here's a proof that it's not possible. The proof doesn't require the graph to be a simple one.
Definition: a connected component $A$ of the graph is
a set of nodes such that
- a path exists between any two nodes in $A$, and
$A$ is not a proper subset of any other set of nodes for which such a path exists.
Note that by this definition, an isolated node is also a connected component.
Let $G$ be a graph with $n$ nodes and $k$ edges. Whatever its configuration, we can remove all $k$ edges, leaving a set of $n$ isolated nodes, then restore the edges one by one until we get the original graph.
Now consider what happens each time we add an edge.
There are two possibilities:
- The edge joins two nodes belonging to the same connected component, leaving the number of components unchanged.
- The edge joins two nodes in different components, joining two components together and reducing the number of components by $1$.
Therefore each edge added reduces the number of components by at most $1$.
In reconstructing $G$ we begin with $n$ connected components (the individual nodes), and add $k$ edges. So the number of connected components in $G$ is
$$cge n-k.$$
For $G$ to be connected we require $c=1$, so this becomes
$$1ge n-k,$$
and therefore
$$kge n-1.$$
That is, a connected graph with $n$ nodes has at least $n-1$ edges.
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
$endgroup$
$begingroup$
+1 . Your second bullet point implies the first.
$endgroup$
– Ethan Bolker
Feb 5 at 2:17
$begingroup$
@EthanBolker So it does. Because every pair in a set of one is no pairs. I'll turn the first one into a comment about the second.
$endgroup$
– timtfj
Feb 5 at 2:20
$begingroup$
Your second bullet isn't quite right. You need "maximal" in there somewhere, else every pair of vertices connected by an edge is a connected component.
$endgroup$
– Ethan Bolker
Feb 5 at 2:28
$begingroup$
Ahhh thanks. I'll add its meaning since I'm new to the subject (that way I can be confident of being correct)
$endgroup$
– timtfj
Feb 5 at 2:34
$begingroup$
@EthanBolker "and which is not s proper subset of any other connected component"?
$endgroup$
– timtfj
Feb 5 at 2:36
|
show 3 more comments
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%2f3089756%2fcould-a-graph-with-n1-vertices-and-mn-1-edges-be-connected%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
$begingroup$
Here's a proof that it's not possible. The proof doesn't require the graph to be a simple one.
Definition: a connected component $A$ of the graph is
a set of nodes such that
- a path exists between any two nodes in $A$, and
$A$ is not a proper subset of any other set of nodes for which such a path exists.
Note that by this definition, an isolated node is also a connected component.
Let $G$ be a graph with $n$ nodes and $k$ edges. Whatever its configuration, we can remove all $k$ edges, leaving a set of $n$ isolated nodes, then restore the edges one by one until we get the original graph.
Now consider what happens each time we add an edge.
There are two possibilities:
- The edge joins two nodes belonging to the same connected component, leaving the number of components unchanged.
- The edge joins two nodes in different components, joining two components together and reducing the number of components by $1$.
Therefore each edge added reduces the number of components by at most $1$.
In reconstructing $G$ we begin with $n$ connected components (the individual nodes), and add $k$ edges. So the number of connected components in $G$ is
$$cge n-k.$$
For $G$ to be connected we require $c=1$, so this becomes
$$1ge n-k,$$
and therefore
$$kge n-1.$$
That is, a connected graph with $n$ nodes has at least $n-1$ edges.
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
$endgroup$
$begingroup$
+1 . Your second bullet point implies the first.
$endgroup$
– Ethan Bolker
Feb 5 at 2:17
$begingroup$
@EthanBolker So it does. Because every pair in a set of one is no pairs. I'll turn the first one into a comment about the second.
$endgroup$
– timtfj
Feb 5 at 2:20
$begingroup$
Your second bullet isn't quite right. You need "maximal" in there somewhere, else every pair of vertices connected by an edge is a connected component.
$endgroup$
– Ethan Bolker
Feb 5 at 2:28
$begingroup$
Ahhh thanks. I'll add its meaning since I'm new to the subject (that way I can be confident of being correct)
$endgroup$
– timtfj
Feb 5 at 2:34
$begingroup$
@EthanBolker "and which is not s proper subset of any other connected component"?
$endgroup$
– timtfj
Feb 5 at 2:36
|
show 3 more comments
$begingroup$
Here's a proof that it's not possible. The proof doesn't require the graph to be a simple one.
Definition: a connected component $A$ of the graph is
a set of nodes such that
- a path exists between any two nodes in $A$, and
$A$ is not a proper subset of any other set of nodes for which such a path exists.
Note that by this definition, an isolated node is also a connected component.
Let $G$ be a graph with $n$ nodes and $k$ edges. Whatever its configuration, we can remove all $k$ edges, leaving a set of $n$ isolated nodes, then restore the edges one by one until we get the original graph.
Now consider what happens each time we add an edge.
There are two possibilities:
- The edge joins two nodes belonging to the same connected component, leaving the number of components unchanged.
- The edge joins two nodes in different components, joining two components together and reducing the number of components by $1$.
Therefore each edge added reduces the number of components by at most $1$.
In reconstructing $G$ we begin with $n$ connected components (the individual nodes), and add $k$ edges. So the number of connected components in $G$ is
$$cge n-k.$$
For $G$ to be connected we require $c=1$, so this becomes
$$1ge n-k,$$
and therefore
$$kge n-1.$$
That is, a connected graph with $n$ nodes has at least $n-1$ edges.
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
$endgroup$
$begingroup$
+1 . Your second bullet point implies the first.
$endgroup$
– Ethan Bolker
Feb 5 at 2:17
$begingroup$
@EthanBolker So it does. Because every pair in a set of one is no pairs. I'll turn the first one into a comment about the second.
$endgroup$
– timtfj
Feb 5 at 2:20
$begingroup$
Your second bullet isn't quite right. You need "maximal" in there somewhere, else every pair of vertices connected by an edge is a connected component.
$endgroup$
– Ethan Bolker
Feb 5 at 2:28
$begingroup$
Ahhh thanks. I'll add its meaning since I'm new to the subject (that way I can be confident of being correct)
$endgroup$
– timtfj
Feb 5 at 2:34
$begingroup$
@EthanBolker "and which is not s proper subset of any other connected component"?
$endgroup$
– timtfj
Feb 5 at 2:36
|
show 3 more comments
$begingroup$
Here's a proof that it's not possible. The proof doesn't require the graph to be a simple one.
Definition: a connected component $A$ of the graph is
a set of nodes such that
- a path exists between any two nodes in $A$, and
$A$ is not a proper subset of any other set of nodes for which such a path exists.
Note that by this definition, an isolated node is also a connected component.
Let $G$ be a graph with $n$ nodes and $k$ edges. Whatever its configuration, we can remove all $k$ edges, leaving a set of $n$ isolated nodes, then restore the edges one by one until we get the original graph.
Now consider what happens each time we add an edge.
There are two possibilities:
- The edge joins two nodes belonging to the same connected component, leaving the number of components unchanged.
- The edge joins two nodes in different components, joining two components together and reducing the number of components by $1$.
Therefore each edge added reduces the number of components by at most $1$.
In reconstructing $G$ we begin with $n$ connected components (the individual nodes), and add $k$ edges. So the number of connected components in $G$ is
$$cge n-k.$$
For $G$ to be connected we require $c=1$, so this becomes
$$1ge n-k,$$
and therefore
$$kge n-1.$$
That is, a connected graph with $n$ nodes has at least $n-1$ edges.
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
$endgroup$
Here's a proof that it's not possible. The proof doesn't require the graph to be a simple one.
Definition: a connected component $A$ of the graph is
a set of nodes such that
- a path exists between any two nodes in $A$, and
$A$ is not a proper subset of any other set of nodes for which such a path exists.
Note that by this definition, an isolated node is also a connected component.
Let $G$ be a graph with $n$ nodes and $k$ edges. Whatever its configuration, we can remove all $k$ edges, leaving a set of $n$ isolated nodes, then restore the edges one by one until we get the original graph.
Now consider what happens each time we add an edge.
There are two possibilities:
- The edge joins two nodes belonging to the same connected component, leaving the number of components unchanged.
- The edge joins two nodes in different components, joining two components together and reducing the number of components by $1$.
Therefore each edge added reduces the number of components by at most $1$.
In reconstructing $G$ we begin with $n$ connected components (the individual nodes), and add $k$ edges. So the number of connected components in $G$ is
$$cge n-k.$$
For $G$ to be connected we require $c=1$, so this becomes
$$1ge n-k,$$
and therefore
$$kge n-1.$$
That is, a connected graph with $n$ nodes has at least $n-1$ edges.
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
edited Feb 5 at 2:41
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
answered Feb 5 at 1:56
timtfjtimtfj
2,478420
2,478420
$begingroup$
+1 . Your second bullet point implies the first.
$endgroup$
– Ethan Bolker
Feb 5 at 2:17
$begingroup$
@EthanBolker So it does. Because every pair in a set of one is no pairs. I'll turn the first one into a comment about the second.
$endgroup$
– timtfj
Feb 5 at 2:20
$begingroup$
Your second bullet isn't quite right. You need "maximal" in there somewhere, else every pair of vertices connected by an edge is a connected component.
$endgroup$
– Ethan Bolker
Feb 5 at 2:28
$begingroup$
Ahhh thanks. I'll add its meaning since I'm new to the subject (that way I can be confident of being correct)
$endgroup$
– timtfj
Feb 5 at 2:34
$begingroup$
@EthanBolker "and which is not s proper subset of any other connected component"?
$endgroup$
– timtfj
Feb 5 at 2:36
|
show 3 more comments
$begingroup$
+1 . Your second bullet point implies the first.
$endgroup$
– Ethan Bolker
Feb 5 at 2:17
$begingroup$
@EthanBolker So it does. Because every pair in a set of one is no pairs. I'll turn the first one into a comment about the second.
$endgroup$
– timtfj
Feb 5 at 2:20
$begingroup$
Your second bullet isn't quite right. You need "maximal" in there somewhere, else every pair of vertices connected by an edge is a connected component.
$endgroup$
– Ethan Bolker
Feb 5 at 2:28
$begingroup$
Ahhh thanks. I'll add its meaning since I'm new to the subject (that way I can be confident of being correct)
$endgroup$
– timtfj
Feb 5 at 2:34
$begingroup$
@EthanBolker "and which is not s proper subset of any other connected component"?
$endgroup$
– timtfj
Feb 5 at 2:36
$begingroup$
+1 . Your second bullet point implies the first.
$endgroup$
– Ethan Bolker
Feb 5 at 2:17
$begingroup$
+1 . Your second bullet point implies the first.
$endgroup$
– Ethan Bolker
Feb 5 at 2:17
$begingroup$
@EthanBolker So it does. Because every pair in a set of one is no pairs. I'll turn the first one into a comment about the second.
$endgroup$
– timtfj
Feb 5 at 2:20
$begingroup$
@EthanBolker So it does. Because every pair in a set of one is no pairs. I'll turn the first one into a comment about the second.
$endgroup$
– timtfj
Feb 5 at 2:20
$begingroup$
Your second bullet isn't quite right. You need "maximal" in there somewhere, else every pair of vertices connected by an edge is a connected component.
$endgroup$
– Ethan Bolker
Feb 5 at 2:28
$begingroup$
Your second bullet isn't quite right. You need "maximal" in there somewhere, else every pair of vertices connected by an edge is a connected component.
$endgroup$
– Ethan Bolker
Feb 5 at 2:28
$begingroup$
Ahhh thanks. I'll add its meaning since I'm new to the subject (that way I can be confident of being correct)
$endgroup$
– timtfj
Feb 5 at 2:34
$begingroup$
Ahhh thanks. I'll add its meaning since I'm new to the subject (that way I can be confident of being correct)
$endgroup$
– timtfj
Feb 5 at 2:34
$begingroup$
@EthanBolker "and which is not s proper subset of any other connected component"?
$endgroup$
– timtfj
Feb 5 at 2:36
$begingroup$
@EthanBolker "and which is not s proper subset of any other connected component"?
$endgroup$
– timtfj
Feb 5 at 2:36
|
show 3 more comments
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%2f3089756%2fcould-a-graph-with-n1-vertices-and-mn-1-edges-be-connected%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$
A connected graph with $n$ vertices and $n-1$ edges is a tree. Or, consider the spanning tree of the graph.
$endgroup$
– saulspatz
Jan 27 at 16:18
$begingroup$
I had thought about this. In fact by removing a further edge (according to our hypotheses) the tree is no longer connected. But is it a good demonstration to use the example of the tree?
$endgroup$
– Jack
Jan 27 at 16:19
3
$begingroup$
Crossing comments. If the graph is connected, it has a spanning tree, but the spanning tree has $n-1$ edges, contradiction.
$endgroup$
– saulspatz
Jan 27 at 16:21
1
$begingroup$
In practice, though, we use this result to prove properties of trees (such as existence of spanning trees, and the number of edges in a tree) and not vice versa.
$endgroup$
– Misha Lavrov
Jan 27 at 17:02
$begingroup$
Hint: prove that a connected graph with n vertices has at least n−1 edges
$endgroup$
– W.R.P.S
Jan 27 at 21:17