Mixing
prove that a connected graph with $n$ vertices has at least $n-1$ edges
$begingroup$
Show that every connected graph with $n$ vertices has at least $n − 1$ edges.
How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges:
a-----b-----c
with $a$, $b$ and $c$ being vertices, and ${a,b}$, ${b,c}$ being edges.
Is there some way to prove this logically?
--UPDATE--
Does this look correct? Any advice on how to improve this proof would be appreciated. Thank you.
graph-theory discrete-mathematics
$endgroup$
add a comment |
$begingroup$
Show that every connected graph with $n$ vertices has at least $n − 1$ edges.
How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges:
a-----b-----c
with $a$, $b$ and $c$ being vertices, and ${a,b}$, ${b,c}$ being edges.
Is there some way to prove this logically?
--UPDATE--
Does this look correct? Any advice on how to improve this proof would be appreciated. Thank you.
graph-theory discrete-mathematics
$endgroup$
$begingroup$
I'm not sure what background material you have to show this, but here is a hint: trees! One way to think of it is to consider the spanning tree of a connected graph.
$endgroup$
– angryavian
Aug 1 '13 at 7:42
$begingroup$
Do you know that every tree with $n$ vertices has exactly $n-1$ edges?
$endgroup$
– Brian M. Scott
Aug 1 '13 at 7:43
$begingroup$
I don't know...
$endgroup$
– user87509
Aug 1 '13 at 7:46
$begingroup$
Prove by induction that every connected undirected graph with n vertices has at least n-1 edges. (But I am somewhat hesitant to close this as a duplicate of that question, since the OP in the other question was asking about specific hint he was given in his assignment.)
$endgroup$
– Martin Sleziak
Aug 1 '13 at 8:12
$begingroup$
"Also by Axiom 1, we can see that a graph with n-1 edges has one component, which implies that the graph is connected" - this is false. Axiom 1 states that a graph with n vertices and n-1 edges has AT LEAST n-(n-1)=1 component, NOT 1 component. The proof is almost correct though: if the number of components is at least n-m, that means n-m <= number of components = 1 (in the case of a connected graph), so m >= n-1. This is what you wanted to prove.
$endgroup$
– Cat
Dec 29 '13 at 7:26
add a comment |
$begingroup$
Show that every connected graph with $n$ vertices has at least $n − 1$ edges.
How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges:
a-----b-----c
with $a$, $b$ and $c$ being vertices, and ${a,b}$, ${b,c}$ being edges.
Is there some way to prove this logically?
--UPDATE--
Does this look correct? Any advice on how to improve this proof would be appreciated. Thank you.
graph-theory discrete-mathematics
$endgroup$
Show that every connected graph with $n$ vertices has at least $n − 1$ edges.
How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges:
a-----b-----c
with $a$, $b$ and $c$ being vertices, and ${a,b}$, ${b,c}$ being edges.
Is there some way to prove this logically?
--UPDATE--
Does this look correct? Any advice on how to improve this proof would be appreciated. Thank you.
graph-theory discrete-mathematics
graph-theory discrete-mathematics
edited Aug 1 '13 at 9:38
asked Aug 1 '13 at 7:35
user87509
$begingroup$
I'm not sure what background material you have to show this, but here is a hint: trees! One way to think of it is to consider the spanning tree of a connected graph.
$endgroup$
– angryavian
Aug 1 '13 at 7:42
$begingroup$
Do you know that every tree with $n$ vertices has exactly $n-1$ edges?
$endgroup$
– Brian M. Scott
Aug 1 '13 at 7:43
$begingroup$
I don't know...
$endgroup$
– user87509
Aug 1 '13 at 7:46
$begingroup$
Prove by induction that every connected undirected graph with n vertices has at least n-1 edges. (But I am somewhat hesitant to close this as a duplicate of that question, since the OP in the other question was asking about specific hint he was given in his assignment.)
$endgroup$
– Martin Sleziak
Aug 1 '13 at 8:12
$begingroup$
"Also by Axiom 1, we can see that a graph with n-1 edges has one component, which implies that the graph is connected" - this is false. Axiom 1 states that a graph with n vertices and n-1 edges has AT LEAST n-(n-1)=1 component, NOT 1 component. The proof is almost correct though: if the number of components is at least n-m, that means n-m <= number of components = 1 (in the case of a connected graph), so m >= n-1. This is what you wanted to prove.
$endgroup$
– Cat
Dec 29 '13 at 7:26
add a comment |
$begingroup$
I'm not sure what background material you have to show this, but here is a hint: trees! One way to think of it is to consider the spanning tree of a connected graph.
$endgroup$
– angryavian
Aug 1 '13 at 7:42
$begingroup$
Do you know that every tree with $n$ vertices has exactly $n-1$ edges?
$endgroup$
– Brian M. Scott
Aug 1 '13 at 7:43
$begingroup$
I don't know...
$endgroup$
– user87509
Aug 1 '13 at 7:46
$begingroup$
Prove by induction that every connected undirected graph with n vertices has at least n-1 edges. (But I am somewhat hesitant to close this as a duplicate of that question, since the OP in the other question was asking about specific hint he was given in his assignment.)
$endgroup$
– Martin Sleziak
Aug 1 '13 at 8:12
$begingroup$
"Also by Axiom 1, we can see that a graph with n-1 edges has one component, which implies that the graph is connected" - this is false. Axiom 1 states that a graph with n vertices and n-1 edges has AT LEAST n-(n-1)=1 component, NOT 1 component. The proof is almost correct though: if the number of components is at least n-m, that means n-m <= number of components = 1 (in the case of a connected graph), so m >= n-1. This is what you wanted to prove.
$endgroup$
– Cat
Dec 29 '13 at 7:26
$begingroup$
I'm not sure what background material you have to show this, but here is a hint: trees! One way to think of it is to consider the spanning tree of a connected graph.
$endgroup$
– angryavian
Aug 1 '13 at 7:42
$begingroup$
I'm not sure what background material you have to show this, but here is a hint: trees! One way to think of it is to consider the spanning tree of a connected graph.
$endgroup$
– angryavian
Aug 1 '13 at 7:42
$begingroup$
Do you know that every tree with $n$ vertices has exactly $n-1$ edges?
$endgroup$
– Brian M. Scott
Aug 1 '13 at 7:43
$begingroup$
Do you know that every tree with $n$ vertices has exactly $n-1$ edges?
$endgroup$
– Brian M. Scott
Aug 1 '13 at 7:43
$begingroup$
I don't know...
$endgroup$
– user87509
Aug 1 '13 at 7:46
$begingroup$
I don't know...
$endgroup$
– user87509
Aug 1 '13 at 7:46
$begingroup$
Prove by induction that every connected undirected graph with n vertices has at least n-1 edges. (But I am somewhat hesitant to close this as a duplicate of that question, since the OP in the other question was asking about specific hint he was given in his assignment.)
$endgroup$
– Martin Sleziak
Aug 1 '13 at 8:12
$begingroup$
Prove by induction that every connected undirected graph with n vertices has at least n-1 edges. (But I am somewhat hesitant to close this as a duplicate of that question, since the OP in the other question was asking about specific hint he was given in his assignment.)
$endgroup$
– Martin Sleziak
Aug 1 '13 at 8:12
$begingroup$
"Also by Axiom 1, we can see that a graph with n-1 edges has one component, which implies that the graph is connected" - this is false. Axiom 1 states that a graph with n vertices and n-1 edges has AT LEAST n-(n-1)=1 component, NOT 1 component. The proof is almost correct though: if the number of components is at least n-m, that means n-m <= number of components = 1 (in the case of a connected graph), so m >= n-1. This is what you wanted to prove.
$endgroup$
– Cat
Dec 29 '13 at 7:26
$begingroup$
"Also by Axiom 1, we can see that a graph with n-1 edges has one component, which implies that the graph is connected" - this is false. Axiom 1 states that a graph with n vertices and n-1 edges has AT LEAST n-(n-1)=1 component, NOT 1 component. The proof is almost correct though: if the number of components is at least n-m, that means n-m <= number of components = 1 (in the case of a connected graph), so m >= n-1. This is what you wanted to prove.
$endgroup$
– Cat
Dec 29 '13 at 7:26
add a comment |
8 Answers
8
active
oldest
votes
$begingroup$
A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.
Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds.
If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
add a comment |
$begingroup$
There are two standard approaches:
Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).
Induction on the size of the graph. Assume you have a connected graph of $n$ vertices and $m$ edges. Remove the edges until your graph splits in two parts. By inductive hypothesis both parts have at least $n_1 - 1$ and $n_2 - 1$ edges (where $n_1+n_2 = n$), so your graph had at least $n_1 -1 + n_2 - 1 + 1 = n - 1$ edges (the additional one denotes the last edge you removed before the graph stopped being connected).
I hope this helps $ddotsmile$
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
$endgroup$
$begingroup$
How would you prove that such edge or edges exist for whichRemove the edges until your graph splits in two parts.holds in every connected graph ?
$endgroup$
– Breaking Benjamin
Jun 15 '18 at 0:25
$begingroup$
@BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens.
$endgroup$
– dtldarek
Jun 15 '18 at 7:44
add a comment |
$begingroup$
Let $V = {v_1, v_2, dots, v_n}$ be the set of vertices and consider the $n times (n-1)$ triangle
$$ begin{eqnarray} (v_1, v_2) & (v_1,v_3) & cdots & (v_1, v_n) \ & (v_2, v_3) & cdots & (v_2,v_n) \ & & & ; ; ; ; vdots \ & & &
(v_{n-1}, v_n) end{eqnarray}$$
where each point is associated with a potential edge. Circle an entry, say, if the graph does have an edge. If there are strictly less than $n-1$ edges, because there are $n-1$ rows there must be one of them without any edges. But a row is of the form $(v_i, v_j)$, $i<j$, and there being no edges on it means $v_i$ is not connected. But this means the graph isn't connected. So there are at least $n-1$ edges.
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
$endgroup$
add a comment |
$begingroup$
Let G be a connected Graph :
If G has no cycles then G is connected with no cycles $=> G$ is a Tree.
So $G$ has n-1 edges.
If G has cycles : and $G $ is connected then for every two vertices there is a path between them.
Assuming that $G$ have only one cycle:
lets look at the path : $ v_1,v_2 dots v_n,v_1 $ we can remove the edge $ v_1,v_1$ and we will get a connected sub Graph $ v_1,v_2$ with no cycles and $E(H)+1 =E(G)$ so $E(G)=n$.
And by induction you will get that for every number of cycles n $E(G)ge n$.
So if $G $ has cycles $E(G)=n-1$ else $E(G)ge n$ .
edited Aug 24 '14 at 18:37
GanitK
1035
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
$endgroup$
$begingroup$
Will you check my update and let me know if it's an acceptable proof? Thank you.
$endgroup$
– user87509
Aug 1 '13 at 10:28
add a comment |
$begingroup$
This result is immediate by induction once you have established (as lemma) that in every connected graph with at least two vertices there are at least two vertices that can be individually removed (with all adjacent edges) such that the remaining graph is still connected. (The inductive proof applies removal of such a vertex.) The lemma itself in turn is proved by a fairly easy induction on the number of vertices.
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
$endgroup$
add a comment |
$begingroup$
Hint: Let $Gamma$ be a connected graph. If $T subset Gamma$ is a maximal subtree, then $|E(Gamma)| geq |E(T)|$ and $|V(Gamma)|=|V(T)|$. (Where $E(cdot)$ and $V(cdot)$ is the set of edges and vertices respectively.)
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
$endgroup$
add a comment |
$begingroup$
Consider any arbitrary vertex of the n vertices, call it vertex A. Since the graph is connected, there always exists atleast one simple path(without cycles) from vertex A to all vertices (excluding A). Now for consider two simple paths from A to B and A to C. If B is not same as C, there must be atleast one edge which is different in the two paths. Since atleast n-1(since n-1 vertices excluding A are present) paths exist, n-1 edges are must
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
$endgroup$
$begingroup$
There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges?
$endgroup$
– hardmath
Jan 20 at 16:41
add a comment |
$begingroup$
We can use Disjoint Sets here. Disjoint Set Data Structure aka Union-Find Data Structure is quite popular in Computer Science (Cycle Detection etc.).
Disjoint Sets of Vertices are very handy in defining connected components in a graph. The number of Disjoint Sets (DS) equals the number of connected components. $v,u in V$ are members of same DS if there is a path from $u$ to $v$.
To construct DSs of a graph, we start with $|V|$ Sets with each $vin V$ representing a DS. Then we add the edges information. For each ${v,u} in E$, we find the DSs to which $v$ and $u$ belong and union the two sets if they lie in different DSs. So for each edge, there is either $1$ or $0$ union operation.
In this setting, since the graph is connected, we must have a single DS at the end. To merge $|V|$ DSs to one, we must have $|V|-1$ Union operations. Hence at least $|V|-1$ edges are required.
Generalisation :
If a graph has $k$ connected components, we must have $|V|-k$ union operations. Hence, $|E| geq |V|-k$ or $|E|+k geq |V|$
answered Jan 20 at 16:20
AroonalokAroonalok
1086
$endgroup$
1
$begingroup$
"Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation.
$endgroup$
– hardmath
Jan 20 at 16:31
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%2f457042%2fprove-that-a-connected-graph-with-n-vertices-has-at-least-n-1-edges%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.
Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds.
If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
add a comment |
$begingroup$
A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.
Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds.
If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
add a comment |
$begingroup$
A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.
Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds.
If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.
Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds.
If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
answered Aug 1 '13 at 9:30
Hagen von EitzenHagen von Eitzen
282k23272505
282k23272505
add a comment |
add a comment |
$begingroup$
There are two standard approaches:
Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).
Induction on the size of the graph. Assume you have a connected graph of $n$ vertices and $m$ edges. Remove the edges until your graph splits in two parts. By inductive hypothesis both parts have at least $n_1 - 1$ and $n_2 - 1$ edges (where $n_1+n_2 = n$), so your graph had at least $n_1 -1 + n_2 - 1 + 1 = n - 1$ edges (the additional one denotes the last edge you removed before the graph stopped being connected).
I hope this helps $ddotsmile$
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
$endgroup$
$begingroup$
How would you prove that such edge or edges exist for whichRemove the edges until your graph splits in two parts.holds in every connected graph ?
$endgroup$
– Breaking Benjamin
Jun 15 '18 at 0:25
$begingroup$
@BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens.
$endgroup$
– dtldarek
Jun 15 '18 at 7:44
add a comment |
$begingroup$
There are two standard approaches:
Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).
Induction on the size of the graph. Assume you have a connected graph of $n$ vertices and $m$ edges. Remove the edges until your graph splits in two parts. By inductive hypothesis both parts have at least $n_1 - 1$ and $n_2 - 1$ edges (where $n_1+n_2 = n$), so your graph had at least $n_1 -1 + n_2 - 1 + 1 = n - 1$ edges (the additional one denotes the last edge you removed before the graph stopped being connected).
I hope this helps $ddotsmile$
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
$endgroup$
$begingroup$
How would you prove that such edge or edges exist for whichRemove the edges until your graph splits in two parts.holds in every connected graph ?
$endgroup$
– Breaking Benjamin
Jun 15 '18 at 0:25
$begingroup$
@BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens.
$endgroup$
– dtldarek
Jun 15 '18 at 7:44
add a comment |
$begingroup$
There are two standard approaches:
Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).
Induction on the size of the graph. Assume you have a connected graph of $n$ vertices and $m$ edges. Remove the edges until your graph splits in two parts. By inductive hypothesis both parts have at least $n_1 - 1$ and $n_2 - 1$ edges (where $n_1+n_2 = n$), so your graph had at least $n_1 -1 + n_2 - 1 + 1 = n - 1$ edges (the additional one denotes the last edge you removed before the graph stopped being connected).
I hope this helps $ddotsmile$
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
$endgroup$
There are two standard approaches:
Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).
Induction on the size of the graph. Assume you have a connected graph of $n$ vertices and $m$ edges. Remove the edges until your graph splits in two parts. By inductive hypothesis both parts have at least $n_1 - 1$ and $n_2 - 1$ edges (where $n_1+n_2 = n$), so your graph had at least $n_1 -1 + n_2 - 1 + 1 = n - 1$ edges (the additional one denotes the last edge you removed before the graph stopped being connected).
I hope this helps $ddotsmile$
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
answered Aug 1 '13 at 8:40
dtldarekdtldarek
32.4k745100
32.4k745100
$begingroup$
How would you prove that such edge or edges exist for whichRemove the edges until your graph splits in two parts.holds in every connected graph ?
$endgroup$
– Breaking Benjamin
Jun 15 '18 at 0:25
$begingroup$
@BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens.
$endgroup$
– dtldarek
Jun 15 '18 at 7:44
add a comment |
$begingroup$
How would you prove that such edge or edges exist for whichRemove the edges until your graph splits in two parts.holds in every connected graph ?
$endgroup$
– Breaking Benjamin
Jun 15 '18 at 0:25
$begingroup$
@BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens.
$endgroup$
– dtldarek
Jun 15 '18 at 7:44
$begingroup$
How would you prove that such edge or edges exist for which
Remove the edges until your graph splits in two parts. holds in every connected graph ?$endgroup$
– Breaking Benjamin
Jun 15 '18 at 0:25
$begingroup$
How would you prove that such edge or edges exist for which
Remove the edges until your graph splits in two parts. holds in every connected graph ?$endgroup$
– Breaking Benjamin
Jun 15 '18 at 0:25
$begingroup$
@BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens.
$endgroup$
– dtldarek
Jun 15 '18 at 7:44
$begingroup$
@BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens.
$endgroup$
– dtldarek
Jun 15 '18 at 7:44
add a comment |
$begingroup$
Let $V = {v_1, v_2, dots, v_n}$ be the set of vertices and consider the $n times (n-1)$ triangle
$$ begin{eqnarray} (v_1, v_2) & (v_1,v_3) & cdots & (v_1, v_n) \ & (v_2, v_3) & cdots & (v_2,v_n) \ & & & ; ; ; ; vdots \ & & &
(v_{n-1}, v_n) end{eqnarray}$$
where each point is associated with a potential edge. Circle an entry, say, if the graph does have an edge. If there are strictly less than $n-1$ edges, because there are $n-1$ rows there must be one of them without any edges. But a row is of the form $(v_i, v_j)$, $i<j$, and there being no edges on it means $v_i$ is not connected. But this means the graph isn't connected. So there are at least $n-1$ edges.
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
$endgroup$
add a comment |
$begingroup$
Let $V = {v_1, v_2, dots, v_n}$ be the set of vertices and consider the $n times (n-1)$ triangle
$$ begin{eqnarray} (v_1, v_2) & (v_1,v_3) & cdots & (v_1, v_n) \ & (v_2, v_3) & cdots & (v_2,v_n) \ & & & ; ; ; ; vdots \ & & &
(v_{n-1}, v_n) end{eqnarray}$$
where each point is associated with a potential edge. Circle an entry, say, if the graph does have an edge. If there are strictly less than $n-1$ edges, because there are $n-1$ rows there must be one of them without any edges. But a row is of the form $(v_i, v_j)$, $i<j$, and there being no edges on it means $v_i$ is not connected. But this means the graph isn't connected. So there are at least $n-1$ edges.
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
$endgroup$
add a comment |
$begingroup$
Let $V = {v_1, v_2, dots, v_n}$ be the set of vertices and consider the $n times (n-1)$ triangle
$$ begin{eqnarray} (v_1, v_2) & (v_1,v_3) & cdots & (v_1, v_n) \ & (v_2, v_3) & cdots & (v_2,v_n) \ & & & ; ; ; ; vdots \ & & &
(v_{n-1}, v_n) end{eqnarray}$$
where each point is associated with a potential edge. Circle an entry, say, if the graph does have an edge. If there are strictly less than $n-1$ edges, because there are $n-1$ rows there must be one of them without any edges. But a row is of the form $(v_i, v_j)$, $i<j$, and there being no edges on it means $v_i$ is not connected. But this means the graph isn't connected. So there are at least $n-1$ edges.
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
$endgroup$
Let $V = {v_1, v_2, dots, v_n}$ be the set of vertices and consider the $n times (n-1)$ triangle
$$ begin{eqnarray} (v_1, v_2) & (v_1,v_3) & cdots & (v_1, v_n) \ & (v_2, v_3) & cdots & (v_2,v_n) \ & & & ; ; ; ; vdots \ & & &
(v_{n-1}, v_n) end{eqnarray}$$
where each point is associated with a potential edge. Circle an entry, say, if the graph does have an edge. If there are strictly less than $n-1$ edges, because there are $n-1$ rows there must be one of them without any edges. But a row is of the form $(v_i, v_j)$, $i<j$, and there being no edges on it means $v_i$ is not connected. But this means the graph isn't connected. So there are at least $n-1$ edges.
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
answered Aug 24 '14 at 18:51
abnryabnry
11.7k22366
11.7k22366
add a comment |
add a comment |
$begingroup$
Let G be a connected Graph :
If G has no cycles then G is connected with no cycles $=> G$ is a Tree.
So $G$ has n-1 edges.
If G has cycles : and $G $ is connected then for every two vertices there is a path between them.
Assuming that $G$ have only one cycle:
lets look at the path : $ v_1,v_2 dots v_n,v_1 $ we can remove the edge $ v_1,v_1$ and we will get a connected sub Graph $ v_1,v_2$ with no cycles and $E(H)+1 =E(G)$ so $E(G)=n$.
And by induction you will get that for every number of cycles n $E(G)ge n$.
So if $G $ has cycles $E(G)=n-1$ else $E(G)ge n$ .
edited Aug 24 '14 at 18:37
GanitK
1035
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
$endgroup$
$begingroup$
Will you check my update and let me know if it's an acceptable proof? Thank you.
$endgroup$
– user87509
Aug 1 '13 at 10:28
add a comment |
$begingroup$
Let G be a connected Graph :
If G has no cycles then G is connected with no cycles $=> G$ is a Tree.
So $G$ has n-1 edges.
If G has cycles : and $G $ is connected then for every two vertices there is a path between them.
Assuming that $G$ have only one cycle:
lets look at the path : $ v_1,v_2 dots v_n,v_1 $ we can remove the edge $ v_1,v_1$ and we will get a connected sub Graph $ v_1,v_2$ with no cycles and $E(H)+1 =E(G)$ so $E(G)=n$.
And by induction you will get that for every number of cycles n $E(G)ge n$.
So if $G $ has cycles $E(G)=n-1$ else $E(G)ge n$ .
edited Aug 24 '14 at 18:37
GanitK
1035
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
$endgroup$
$begingroup$
Will you check my update and let me know if it's an acceptable proof? Thank you.
$endgroup$
– user87509
Aug 1 '13 at 10:28
add a comment |
$begingroup$
Let G be a connected Graph :
If G has no cycles then G is connected with no cycles $=> G$ is a Tree.
So $G$ has n-1 edges.
If G has cycles : and $G $ is connected then for every two vertices there is a path between them.
Assuming that $G$ have only one cycle:
lets look at the path : $ v_1,v_2 dots v_n,v_1 $ we can remove the edge $ v_1,v_1$ and we will get a connected sub Graph $ v_1,v_2$ with no cycles and $E(H)+1 =E(G)$ so $E(G)=n$.
And by induction you will get that for every number of cycles n $E(G)ge n$.
So if $G $ has cycles $E(G)=n-1$ else $E(G)ge n$ .
edited Aug 24 '14 at 18:37
GanitK
1035
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
$endgroup$
Let G be a connected Graph :
If G has no cycles then G is connected with no cycles $=> G$ is a Tree.
So $G$ has n-1 edges.
If G has cycles : and $G $ is connected then for every two vertices there is a path between them.
Assuming that $G$ have only one cycle:
lets look at the path : $ v_1,v_2 dots v_n,v_1 $ we can remove the edge $ v_1,v_1$ and we will get a connected sub Graph $ v_1,v_2$ with no cycles and $E(H)+1 =E(G)$ so $E(G)=n$.
And by induction you will get that for every number of cycles n $E(G)ge n$.
So if $G $ has cycles $E(G)=n-1$ else $E(G)ge n$ .
edited Aug 24 '14 at 18:37
GanitK
1035
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
edited Aug 24 '14 at 18:37
GanitK
1035
edited Aug 24 '14 at 18:37
GanitK
1035
edited Aug 24 '14 at 18:37
GanitK
1035
1035
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
answered Aug 1 '13 at 8:10
Eli ElizirovEli Elizirov
1,505618
1,505618
$begingroup$
Will you check my update and let me know if it's an acceptable proof? Thank you.
$endgroup$
– user87509
Aug 1 '13 at 10:28
add a comment |
$begingroup$
Will you check my update and let me know if it's an acceptable proof? Thank you.
$endgroup$
– user87509
Aug 1 '13 at 10:28
$begingroup$
Will you check my update and let me know if it's an acceptable proof? Thank you.
$endgroup$
– user87509
Aug 1 '13 at 10:28
$begingroup$
Will you check my update and let me know if it's an acceptable proof? Thank you.
$endgroup$
– user87509
Aug 1 '13 at 10:28
add a comment |
$begingroup$
This result is immediate by induction once you have established (as lemma) that in every connected graph with at least two vertices there are at least two vertices that can be individually removed (with all adjacent edges) such that the remaining graph is still connected. (The inductive proof applies removal of such a vertex.) The lemma itself in turn is proved by a fairly easy induction on the number of vertices.
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
$endgroup$
add a comment |
$begingroup$
This result is immediate by induction once you have established (as lemma) that in every connected graph with at least two vertices there are at least two vertices that can be individually removed (with all adjacent edges) such that the remaining graph is still connected. (The inductive proof applies removal of such a vertex.) The lemma itself in turn is proved by a fairly easy induction on the number of vertices.
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
$endgroup$
add a comment |
$begingroup$
This result is immediate by induction once you have established (as lemma) that in every connected graph with at least two vertices there are at least two vertices that can be individually removed (with all adjacent edges) such that the remaining graph is still connected. (The inductive proof applies removal of such a vertex.) The lemma itself in turn is proved by a fairly easy induction on the number of vertices.
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
$endgroup$
This result is immediate by induction once you have established (as lemma) that in every connected graph with at least two vertices there are at least two vertices that can be individually removed (with all adjacent edges) such that the remaining graph is still connected. (The inductive proof applies removal of such a vertex.) The lemma itself in turn is proved by a fairly easy induction on the number of vertices.
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
edited Aug 1 '13 at 20:33
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
answered Aug 1 '13 at 8:09
Marc van LeeuwenMarc van Leeuwen
87.7k5110225
87.7k5110225
add a comment |
add a comment |
$begingroup$
Hint: Let $Gamma$ be a connected graph. If $T subset Gamma$ is a maximal subtree, then $|E(Gamma)| geq |E(T)|$ and $|V(Gamma)|=|V(T)|$. (Where $E(cdot)$ and $V(cdot)$ is the set of edges and vertices respectively.)
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
$endgroup$
add a comment |
$begingroup$
Hint: Let $Gamma$ be a connected graph. If $T subset Gamma$ is a maximal subtree, then $|E(Gamma)| geq |E(T)|$ and $|V(Gamma)|=|V(T)|$. (Where $E(cdot)$ and $V(cdot)$ is the set of edges and vertices respectively.)
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
$endgroup$
add a comment |
$begingroup$
Hint: Let $Gamma$ be a connected graph. If $T subset Gamma$ is a maximal subtree, then $|E(Gamma)| geq |E(T)|$ and $|V(Gamma)|=|V(T)|$. (Where $E(cdot)$ and $V(cdot)$ is the set of edges and vertices respectively.)
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
$endgroup$
Hint: Let $Gamma$ be a connected graph. If $T subset Gamma$ is a maximal subtree, then $|E(Gamma)| geq |E(T)|$ and $|V(Gamma)|=|V(T)|$. (Where $E(cdot)$ and $V(cdot)$ is the set of edges and vertices respectively.)
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
answered Aug 1 '13 at 7:43
SeiriosSeirios
24.2k347100
24.2k347100
add a comment |
add a comment |
$begingroup$
Consider any arbitrary vertex of the n vertices, call it vertex A. Since the graph is connected, there always exists atleast one simple path(without cycles) from vertex A to all vertices (excluding A). Now for consider two simple paths from A to B and A to C. If B is not same as C, there must be atleast one edge which is different in the two paths. Since atleast n-1(since n-1 vertices excluding A are present) paths exist, n-1 edges are must
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
$endgroup$
$begingroup$
There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges?
$endgroup$
– hardmath
Jan 20 at 16:41
add a comment |
$begingroup$
Consider any arbitrary vertex of the n vertices, call it vertex A. Since the graph is connected, there always exists atleast one simple path(without cycles) from vertex A to all vertices (excluding A). Now for consider two simple paths from A to B and A to C. If B is not same as C, there must be atleast one edge which is different in the two paths. Since atleast n-1(since n-1 vertices excluding A are present) paths exist, n-1 edges are must
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
$endgroup$
$begingroup$
There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges?
$endgroup$
– hardmath
Jan 20 at 16:41
add a comment |
$begingroup$
Consider any arbitrary vertex of the n vertices, call it vertex A. Since the graph is connected, there always exists atleast one simple path(without cycles) from vertex A to all vertices (excluding A). Now for consider two simple paths from A to B and A to C. If B is not same as C, there must be atleast one edge which is different in the two paths. Since atleast n-1(since n-1 vertices excluding A are present) paths exist, n-1 edges are must
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
$endgroup$
Consider any arbitrary vertex of the n vertices, call it vertex A. Since the graph is connected, there always exists atleast one simple path(without cycles) from vertex A to all vertices (excluding A). Now for consider two simple paths from A to B and A to C. If B is not same as C, there must be atleast one edge which is different in the two paths. Since atleast n-1(since n-1 vertices excluding A are present) paths exist, n-1 edges are must
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
answered Nov 12 '18 at 12:26
Sameer PandeSameer Pande
1
1
$begingroup$
There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges?
$endgroup$
– hardmath
Jan 20 at 16:41
add a comment |
$begingroup$
There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges?
$endgroup$
– hardmath
Jan 20 at 16:41
$begingroup$
There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges?
$endgroup$
– hardmath
Jan 20 at 16:41
$begingroup$
There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges?
$endgroup$
– hardmath
Jan 20 at 16:41
add a comment |
$begingroup$
We can use Disjoint Sets here. Disjoint Set Data Structure aka Union-Find Data Structure is quite popular in Computer Science (Cycle Detection etc.).
Disjoint Sets of Vertices are very handy in defining connected components in a graph. The number of Disjoint Sets (DS) equals the number of connected components. $v,u in V$ are members of same DS if there is a path from $u$ to $v$.
To construct DSs of a graph, we start with $|V|$ Sets with each $vin V$ representing a DS. Then we add the edges information. For each ${v,u} in E$, we find the DSs to which $v$ and $u$ belong and union the two sets if they lie in different DSs. So for each edge, there is either $1$ or $0$ union operation.
In this setting, since the graph is connected, we must have a single DS at the end. To merge $|V|$ DSs to one, we must have $|V|-1$ Union operations. Hence at least $|V|-1$ edges are required.
Generalisation :
If a graph has $k$ connected components, we must have $|V|-k$ union operations. Hence, $|E| geq |V|-k$ or $|E|+k geq |V|$
answered Jan 20 at 16:20
AroonalokAroonalok
1086
$endgroup$
1
$begingroup$
"Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation.
$endgroup$
– hardmath
Jan 20 at 16:31
add a comment |
$begingroup$
We can use Disjoint Sets here. Disjoint Set Data Structure aka Union-Find Data Structure is quite popular in Computer Science (Cycle Detection etc.).
Disjoint Sets of Vertices are very handy in defining connected components in a graph. The number of Disjoint Sets (DS) equals the number of connected components. $v,u in V$ are members of same DS if there is a path from $u$ to $v$.
To construct DSs of a graph, we start with $|V|$ Sets with each $vin V$ representing a DS. Then we add the edges information. For each ${v,u} in E$, we find the DSs to which $v$ and $u$ belong and union the two sets if they lie in different DSs. So for each edge, there is either $1$ or $0$ union operation.
In this setting, since the graph is connected, we must have a single DS at the end. To merge $|V|$ DSs to one, we must have $|V|-1$ Union operations. Hence at least $|V|-1$ edges are required.
Generalisation :
If a graph has $k$ connected components, we must have $|V|-k$ union operations. Hence, $|E| geq |V|-k$ or $|E|+k geq |V|$
answered Jan 20 at 16:20
AroonalokAroonalok
1086
$endgroup$
1
$begingroup$
"Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation.
$endgroup$
– hardmath
Jan 20 at 16:31
add a comment |
$begingroup$
We can use Disjoint Sets here. Disjoint Set Data Structure aka Union-Find Data Structure is quite popular in Computer Science (Cycle Detection etc.).
Disjoint Sets of Vertices are very handy in defining connected components in a graph. The number of Disjoint Sets (DS) equals the number of connected components. $v,u in V$ are members of same DS if there is a path from $u$ to $v$.
To construct DSs of a graph, we start with $|V|$ Sets with each $vin V$ representing a DS. Then we add the edges information. For each ${v,u} in E$, we find the DSs to which $v$ and $u$ belong and union the two sets if they lie in different DSs. So for each edge, there is either $1$ or $0$ union operation.
In this setting, since the graph is connected, we must have a single DS at the end. To merge $|V|$ DSs to one, we must have $|V|-1$ Union operations. Hence at least $|V|-1$ edges are required.
Generalisation :
If a graph has $k$ connected components, we must have $|V|-k$ union operations. Hence, $|E| geq |V|-k$ or $|E|+k geq |V|$
answered Jan 20 at 16:20
AroonalokAroonalok
1086
$endgroup$
We can use Disjoint Sets here. Disjoint Set Data Structure aka Union-Find Data Structure is quite popular in Computer Science (Cycle Detection etc.).
Disjoint Sets of Vertices are very handy in defining connected components in a graph. The number of Disjoint Sets (DS) equals the number of connected components. $v,u in V$ are members of same DS if there is a path from $u$ to $v$.
To construct DSs of a graph, we start with $|V|$ Sets with each $vin V$ representing a DS. Then we add the edges information. For each ${v,u} in E$, we find the DSs to which $v$ and $u$ belong and union the two sets if they lie in different DSs. So for each edge, there is either $1$ or $0$ union operation.
In this setting, since the graph is connected, we must have a single DS at the end. To merge $|V|$ DSs to one, we must have $|V|-1$ Union operations. Hence at least $|V|-1$ edges are required.
Generalisation :
If a graph has $k$ connected components, we must have $|V|-k$ union operations. Hence, $|E| geq |V|-k$ or $|E|+k geq |V|$
answered Jan 20 at 16:20
AroonalokAroonalok
1086
edited Jan 20 at 16:52
answered Jan 20 at 16:20
AroonalokAroonalok
1086
answered Jan 20 at 16:20
AroonalokAroonalok
1086
answered Jan 20 at 16:20
AroonalokAroonalok
1086
1086
1
$begingroup$
"Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation.
$endgroup$
– hardmath
Jan 20 at 16:31
add a comment |
1
$begingroup$
"Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation.
$endgroup$
– hardmath
Jan 20 at 16:31
1
1
$begingroup$
"Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation.
$endgroup$
– hardmath
Jan 20 at 16:31
$begingroup$
"Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation.
$endgroup$
– hardmath
Jan 20 at 16:31
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%2f457042%2fprove-that-a-connected-graph-with-n-vertices-has-at-least-n-1-edges%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$
I'm not sure what background material you have to show this, but here is a hint: trees! One way to think of it is to consider the spanning tree of a connected graph.
$endgroup$
– angryavian
Aug 1 '13 at 7:42
$begingroup$
Do you know that every tree with $n$ vertices has exactly $n-1$ edges?
$endgroup$
– Brian M. Scott
Aug 1 '13 at 7:43
$begingroup$
I don't know...
$endgroup$
– user87509
Aug 1 '13 at 7:46
$begingroup$
Prove by induction that every connected undirected graph with n vertices has at least n-1 edges. (But I am somewhat hesitant to close this as a duplicate of that question, since the OP in the other question was asking about specific hint he was given in his assignment.)
$endgroup$
– Martin Sleziak
Aug 1 '13 at 8:12
$begingroup$
"Also by Axiom 1, we can see that a graph with n-1 edges has one component, which implies that the graph is connected" - this is false. Axiom 1 states that a graph with n vertices and n-1 edges has AT LEAST n-(n-1)=1 component, NOT 1 component. The proof is almost correct though: if the number of components is at least n-m, that means n-m <= number of components = 1 (in the case of a connected graph), so m >= n-1. This is what you wanted to prove.
$endgroup$
– Cat
Dec 29 '13 at 7:26