Mixing
Given a graph $G = (V, E),$ prove that if $|E| > binom{ |V| -1}{2}$ then the graph is connected.
$begingroup$
I know that a similar exercice was already posted on this website but I would like to have a piece of advice concerning the method/way of thinking I used to solve this problem. I don't know if I can do this here or if I have to write in the comment of the exercice that was posted. Pardon in advance.
We have to prove a statement $p Rightarrow q.$ So as to do so I wanted to prove $neg q Rightarrow neg p.$
To solve this problem I first considered that with a graph with $n$ vertices the maximum value of edges that we can get is when we consider the graph as a complete graph . But we have to deal with a disconnected graph. To obtain the maximal value of edges, I split the set of vertices into two partitions $X$ and $Y$ such that $Y$ = {v} where v $in$ $V$. This would mean that $|X| = |V|-1.$
Now, I compute the maximum number of edges that I can obtain from the graph $X: binom{|V| -1}{2}$. As it corresponds to the maximal value of edges that we can obtain (by respecting the conditions of the statement), it means that $|E| leq binom{|V| -1}{2}$.
Ps: I only removed one vertex because: the more I remove vertices, the less edges I will obtain.
Thank you in advance for your comments.
discrete-mathematics graph-theory advice
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
$endgroup$
add a comment |
$begingroup$
I know that a similar exercice was already posted on this website but I would like to have a piece of advice concerning the method/way of thinking I used to solve this problem. I don't know if I can do this here or if I have to write in the comment of the exercice that was posted. Pardon in advance.
We have to prove a statement $p Rightarrow q.$ So as to do so I wanted to prove $neg q Rightarrow neg p.$
To solve this problem I first considered that with a graph with $n$ vertices the maximum value of edges that we can get is when we consider the graph as a complete graph . But we have to deal with a disconnected graph. To obtain the maximal value of edges, I split the set of vertices into two partitions $X$ and $Y$ such that $Y$ = {v} where v $in$ $V$. This would mean that $|X| = |V|-1.$
Now, I compute the maximum number of edges that I can obtain from the graph $X: binom{|V| -1}{2}$. As it corresponds to the maximal value of edges that we can obtain (by respecting the conditions of the statement), it means that $|E| leq binom{|V| -1}{2}$.
Ps: I only removed one vertex because: the more I remove vertices, the less edges I will obtain.
Thank you in advance for your comments.
discrete-mathematics graph-theory advice
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
$endgroup$
2
$begingroup$
math.stackexchange.com/questions/2680559/…
$endgroup$
– greedoid
Jan 20 at 18:28
$begingroup$
greedoid's link will give you an answer, but I also wanted to note some problems with your argument. First, when you write $Y={v|vin V}$, that means $Y=V$ in set theoretic language. What you should say is $Y={v}$ for some $vin V$, which means $Y$ contains only $v$. You also need to argue why partitioning the vertex set into $X$ and $Y$ like that will give the most edges.
$endgroup$
– Kevin Long
Jan 20 at 18:33
$begingroup$
Dear Kevin, thank you for your answer in fact I wrote in the way you proposed but my topic was edited. By the way in case it's not considered as admitted I will prove this by saying that If I consider a graph with 2 component X and Y such that |X| (= p) > |Y| ( = q) then if i remove one vertex from X so as to add it in the set Y the number of edges of this new graph will be lower because ${p-1}choose{2}$ + ${q+1}choose{2}$ <= ${p}choose{2}$ + ${q}choose{2}$.
$endgroup$
– Hugo Peyron
Jan 20 at 19:35
add a comment |
$begingroup$
I know that a similar exercice was already posted on this website but I would like to have a piece of advice concerning the method/way of thinking I used to solve this problem. I don't know if I can do this here or if I have to write in the comment of the exercice that was posted. Pardon in advance.
We have to prove a statement $p Rightarrow q.$ So as to do so I wanted to prove $neg q Rightarrow neg p.$
To solve this problem I first considered that with a graph with $n$ vertices the maximum value of edges that we can get is when we consider the graph as a complete graph . But we have to deal with a disconnected graph. To obtain the maximal value of edges, I split the set of vertices into two partitions $X$ and $Y$ such that $Y$ = {v} where v $in$ $V$. This would mean that $|X| = |V|-1.$
Now, I compute the maximum number of edges that I can obtain from the graph $X: binom{|V| -1}{2}$. As it corresponds to the maximal value of edges that we can obtain (by respecting the conditions of the statement), it means that $|E| leq binom{|V| -1}{2}$.
Ps: I only removed one vertex because: the more I remove vertices, the less edges I will obtain.
Thank you in advance for your comments.
discrete-mathematics graph-theory advice
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
$endgroup$
I know that a similar exercice was already posted on this website but I would like to have a piece of advice concerning the method/way of thinking I used to solve this problem. I don't know if I can do this here or if I have to write in the comment of the exercice that was posted. Pardon in advance.
We have to prove a statement $p Rightarrow q.$ So as to do so I wanted to prove $neg q Rightarrow neg p.$
To solve this problem I first considered that with a graph with $n$ vertices the maximum value of edges that we can get is when we consider the graph as a complete graph . But we have to deal with a disconnected graph. To obtain the maximal value of edges, I split the set of vertices into two partitions $X$ and $Y$ such that $Y$ = {v} where v $in$ $V$. This would mean that $|X| = |V|-1.$
Now, I compute the maximum number of edges that I can obtain from the graph $X: binom{|V| -1}{2}$. As it corresponds to the maximal value of edges that we can obtain (by respecting the conditions of the statement), it means that $|E| leq binom{|V| -1}{2}$.
Ps: I only removed one vertex because: the more I remove vertices, the less edges I will obtain.
Thank you in advance for your comments.
discrete-mathematics graph-theory advice
discrete-mathematics graph-theory advice
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
edited Jan 20 at 18:44
Hugo Peyron
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
asked Jan 20 at 18:14
Hugo PeyronHugo Peyron
244
244
2
$begingroup$
math.stackexchange.com/questions/2680559/…
$endgroup$
– greedoid
Jan 20 at 18:28
$begingroup$
greedoid's link will give you an answer, but I also wanted to note some problems with your argument. First, when you write $Y={v|vin V}$, that means $Y=V$ in set theoretic language. What you should say is $Y={v}$ for some $vin V$, which means $Y$ contains only $v$. You also need to argue why partitioning the vertex set into $X$ and $Y$ like that will give the most edges.
$endgroup$
– Kevin Long
Jan 20 at 18:33
$begingroup$
Dear Kevin, thank you for your answer in fact I wrote in the way you proposed but my topic was edited. By the way in case it's not considered as admitted I will prove this by saying that If I consider a graph with 2 component X and Y such that |X| (= p) > |Y| ( = q) then if i remove one vertex from X so as to add it in the set Y the number of edges of this new graph will be lower because ${p-1}choose{2}$ + ${q+1}choose{2}$ <= ${p}choose{2}$ + ${q}choose{2}$.
$endgroup$
– Hugo Peyron
Jan 20 at 19:35
add a comment |
2
$begingroup$
math.stackexchange.com/questions/2680559/…
$endgroup$
– greedoid
Jan 20 at 18:28
$begingroup$
greedoid's link will give you an answer, but I also wanted to note some problems with your argument. First, when you write $Y={v|vin V}$, that means $Y=V$ in set theoretic language. What you should say is $Y={v}$ for some $vin V$, which means $Y$ contains only $v$. You also need to argue why partitioning the vertex set into $X$ and $Y$ like that will give the most edges.
$endgroup$
– Kevin Long
Jan 20 at 18:33
$begingroup$
Dear Kevin, thank you for your answer in fact I wrote in the way you proposed but my topic was edited. By the way in case it's not considered as admitted I will prove this by saying that If I consider a graph with 2 component X and Y such that |X| (= p) > |Y| ( = q) then if i remove one vertex from X so as to add it in the set Y the number of edges of this new graph will be lower because ${p-1}choose{2}$ + ${q+1}choose{2}$ <= ${p}choose{2}$ + ${q}choose{2}$.
$endgroup$
– Hugo Peyron
Jan 20 at 19:35
2
2
$begingroup$
math.stackexchange.com/questions/2680559/…
$endgroup$
– greedoid
Jan 20 at 18:28
$begingroup$
math.stackexchange.com/questions/2680559/…
$endgroup$
– greedoid
Jan 20 at 18:28
$begingroup$
greedoid's link will give you an answer, but I also wanted to note some problems with your argument. First, when you write $Y={v|vin V}$, that means $Y=V$ in set theoretic language. What you should say is $Y={v}$ for some $vin V$, which means $Y$ contains only $v$. You also need to argue why partitioning the vertex set into $X$ and $Y$ like that will give the most edges.
$endgroup$
– Kevin Long
Jan 20 at 18:33
$begingroup$
greedoid's link will give you an answer, but I also wanted to note some problems with your argument. First, when you write $Y={v|vin V}$, that means $Y=V$ in set theoretic language. What you should say is $Y={v}$ for some $vin V$, which means $Y$ contains only $v$. You also need to argue why partitioning the vertex set into $X$ and $Y$ like that will give the most edges.
$endgroup$
– Kevin Long
Jan 20 at 18:33
$begingroup$
Dear Kevin, thank you for your answer in fact I wrote in the way you proposed but my topic was edited. By the way in case it's not considered as admitted I will prove this by saying that If I consider a graph with 2 component X and Y such that |X| (= p) > |Y| ( = q) then if i remove one vertex from X so as to add it in the set Y the number of edges of this new graph will be lower because ${p-1}choose{2}$ + ${q+1}choose{2}$ <= ${p}choose{2}$ + ${q}choose{2}$.
$endgroup$
– Hugo Peyron
Jan 20 at 19:35
$begingroup$
Dear Kevin, thank you for your answer in fact I wrote in the way you proposed but my topic was edited. By the way in case it's not considered as admitted I will prove this by saying that If I consider a graph with 2 component X and Y such that |X| (= p) > |Y| ( = q) then if i remove one vertex from X so as to add it in the set Y the number of edges of this new graph will be lower because ${p-1}choose{2}$ + ${q+1}choose{2}$ <= ${p}choose{2}$ + ${q}choose{2}$.
$endgroup$
– Hugo Peyron
Jan 20 at 19:35
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If the graph is not connected, then we can write $V=Xcup Y$ where $X,Y$ are non-empty and disjoint and there is no edge between vertices in $X$ and vertices in $Y$. While you are right that ultimately the numerically "worst case" does happen when $Y$ (or $X$) has only one element, you cannot assume in your proof that the sets do have this property to begin with. The structure and size of possible $X,Y$ is iven by the (given, arbitrary) graph and for a concrete graph may exclude that one of them has only one element. So in your proof, you will at some step have to show ${kchoose 2}+{n-kchoose 2}le{n-1choose 2}$ for all $k$ with $1le kle n-1$.
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
$begingroup$
Dear Sir, thank you for your answer. I thought I could majorate this value |E| regardless of the given graph ( I wanted to say that |E| $in$ [0, Max_Value] and by removing only one vertex and considering the partition (with a number of vertices greater than one ) as a complete graph, I will find this Max_Value.
$endgroup$
– Hugo Peyron
Jan 20 at 18:40
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%2f3080934%2fgiven-a-graph-g-v-e-prove-that-if-e-binom-v-12-then-the-gr%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$
If the graph is not connected, then we can write $V=Xcup Y$ where $X,Y$ are non-empty and disjoint and there is no edge between vertices in $X$ and vertices in $Y$. While you are right that ultimately the numerically "worst case" does happen when $Y$ (or $X$) has only one element, you cannot assume in your proof that the sets do have this property to begin with. The structure and size of possible $X,Y$ is iven by the (given, arbitrary) graph and for a concrete graph may exclude that one of them has only one element. So in your proof, you will at some step have to show ${kchoose 2}+{n-kchoose 2}le{n-1choose 2}$ for all $k$ with $1le kle n-1$.
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
$begingroup$
Dear Sir, thank you for your answer. I thought I could majorate this value |E| regardless of the given graph ( I wanted to say that |E| $in$ [0, Max_Value] and by removing only one vertex and considering the partition (with a number of vertices greater than one ) as a complete graph, I will find this Max_Value.
$endgroup$
– Hugo Peyron
Jan 20 at 18:40
add a comment |
$begingroup$
If the graph is not connected, then we can write $V=Xcup Y$ where $X,Y$ are non-empty and disjoint and there is no edge between vertices in $X$ and vertices in $Y$. While you are right that ultimately the numerically "worst case" does happen when $Y$ (or $X$) has only one element, you cannot assume in your proof that the sets do have this property to begin with. The structure and size of possible $X,Y$ is iven by the (given, arbitrary) graph and for a concrete graph may exclude that one of them has only one element. So in your proof, you will at some step have to show ${kchoose 2}+{n-kchoose 2}le{n-1choose 2}$ for all $k$ with $1le kle n-1$.
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
$begingroup$
Dear Sir, thank you for your answer. I thought I could majorate this value |E| regardless of the given graph ( I wanted to say that |E| $in$ [0, Max_Value] and by removing only one vertex and considering the partition (with a number of vertices greater than one ) as a complete graph, I will find this Max_Value.
$endgroup$
– Hugo Peyron
Jan 20 at 18:40
add a comment |
$begingroup$
If the graph is not connected, then we can write $V=Xcup Y$ where $X,Y$ are non-empty and disjoint and there is no edge between vertices in $X$ and vertices in $Y$. While you are right that ultimately the numerically "worst case" does happen when $Y$ (or $X$) has only one element, you cannot assume in your proof that the sets do have this property to begin with. The structure and size of possible $X,Y$ is iven by the (given, arbitrary) graph and for a concrete graph may exclude that one of them has only one element. So in your proof, you will at some step have to show ${kchoose 2}+{n-kchoose 2}le{n-1choose 2}$ for all $k$ with $1le kle n-1$.
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
$endgroup$
If the graph is not connected, then we can write $V=Xcup Y$ where $X,Y$ are non-empty and disjoint and there is no edge between vertices in $X$ and vertices in $Y$. While you are right that ultimately the numerically "worst case" does happen when $Y$ (or $X$) has only one element, you cannot assume in your proof that the sets do have this property to begin with. The structure and size of possible $X,Y$ is iven by the (given, arbitrary) graph and for a concrete graph may exclude that one of them has only one element. So in your proof, you will at some step have to show ${kchoose 2}+{n-kchoose 2}le{n-1choose 2}$ for all $k$ with $1le kle n-1$.
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
answered Jan 20 at 18:33
Hagen von EitzenHagen von Eitzen
282k23272505
282k23272505
$begingroup$
Dear Sir, thank you for your answer. I thought I could majorate this value |E| regardless of the given graph ( I wanted to say that |E| $in$ [0, Max_Value] and by removing only one vertex and considering the partition (with a number of vertices greater than one ) as a complete graph, I will find this Max_Value.
$endgroup$
– Hugo Peyron
Jan 20 at 18:40
add a comment |
$begingroup$
Dear Sir, thank you for your answer. I thought I could majorate this value |E| regardless of the given graph ( I wanted to say that |E| $in$ [0, Max_Value] and by removing only one vertex and considering the partition (with a number of vertices greater than one ) as a complete graph, I will find this Max_Value.
$endgroup$
– Hugo Peyron
Jan 20 at 18:40
$begingroup$
Dear Sir, thank you for your answer. I thought I could majorate this value |E| regardless of the given graph ( I wanted to say that |E| $in$ [0, Max_Value] and by removing only one vertex and considering the partition (with a number of vertices greater than one ) as a complete graph, I will find this Max_Value.
$endgroup$
– Hugo Peyron
Jan 20 at 18:40
$begingroup$
Dear Sir, thank you for your answer. I thought I could majorate this value |E| regardless of the given graph ( I wanted to say that |E| $in$ [0, Max_Value] and by removing only one vertex and considering the partition (with a number of vertices greater than one ) as a complete graph, I will find this Max_Value.
$endgroup$
– Hugo Peyron
Jan 20 at 18:40
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%2f3080934%2fgiven-a-graph-g-v-e-prove-that-if-e-binom-v-12-then-the-gr%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
2
$begingroup$
math.stackexchange.com/questions/2680559/…
$endgroup$
– greedoid
Jan 20 at 18:28
$begingroup$
greedoid's link will give you an answer, but I also wanted to note some problems with your argument. First, when you write $Y={v|vin V}$, that means $Y=V$ in set theoretic language. What you should say is $Y={v}$ for some $vin V$, which means $Y$ contains only $v$. You also need to argue why partitioning the vertex set into $X$ and $Y$ like that will give the most edges.
$endgroup$
– Kevin Long
Jan 20 at 18:33
$begingroup$
Dear Kevin, thank you for your answer in fact I wrote in the way you proposed but my topic was edited. By the way in case it's not considered as admitted I will prove this by saying that If I consider a graph with 2 component X and Y such that |X| (= p) > |Y| ( = q) then if i remove one vertex from X so as to add it in the set Y the number of edges of this new graph will be lower because ${p-1}choose{2}$ + ${q+1}choose{2}$ <= ${p}choose{2}$ + ${q}choose{2}$.
$endgroup$
– Hugo Peyron
Jan 20 at 19:35