Mixing
Prove that for every disconnected graph $G = (V, E)$ it holds $|E| leq frac{1}{2} (|V | − 1)(|V | − 2)$.
up vote
0
down vote
favorite
I have just started my journey into the field of graph theory. I wish to show the following result:
Prove that for every disconnected graph $G = (V, E)$ it holds
$|E| leq frac{1}{2}
(|V| − 1)(|V | − 2)$.
I think the best way to tackle this, is via induction. I want to start with the smallest possible graph you can have, which would be on $2$ vertices, so $n=2$
We know that there are $0$ edges and thus:
$$|E|=0 leq frac{1}{2} (2-1)(2-2)=0. $$
So our base case holds. Now the difficulty would be to assume we have some arbitrary graph for which this formula holds, to then prove it holds for all graphs bigger than this. I cannot possibly construct all bigger graphs. I am guessing there is some different strategy in graph theory to induction proofs.
This result could also follow easily from the handshaking lemma if I assume that $n-1$ vertices have at most degree $n-2$. If someone has an alternative suggestion, please let me know.
graph-theory induction
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
add a comment |
up vote
0
down vote
favorite
I have just started my journey into the field of graph theory. I wish to show the following result:
Prove that for every disconnected graph $G = (V, E)$ it holds
$|E| leq frac{1}{2}
(|V| − 1)(|V | − 2)$.
I think the best way to tackle this, is via induction. I want to start with the smallest possible graph you can have, which would be on $2$ vertices, so $n=2$
We know that there are $0$ edges and thus:
$$|E|=0 leq frac{1}{2} (2-1)(2-2)=0. $$
So our base case holds. Now the difficulty would be to assume we have some arbitrary graph for which this formula holds, to then prove it holds for all graphs bigger than this. I cannot possibly construct all bigger graphs. I am guessing there is some different strategy in graph theory to induction proofs.
This result could also follow easily from the handshaking lemma if I assume that $n-1$ vertices have at most degree $n-2$. If someone has an alternative suggestion, please let me know.
graph-theory induction
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
In your base case, you meant (2-2) instead of (2-0) right?
– mathnoob
yesterday
yes indeed, you are correct.
– WesleyGroupshaveFeelingsToo
yesterday
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have just started my journey into the field of graph theory. I wish to show the following result:
Prove that for every disconnected graph $G = (V, E)$ it holds
$|E| leq frac{1}{2}
(|V| − 1)(|V | − 2)$.
I think the best way to tackle this, is via induction. I want to start with the smallest possible graph you can have, which would be on $2$ vertices, so $n=2$
We know that there are $0$ edges and thus:
$$|E|=0 leq frac{1}{2} (2-1)(2-2)=0. $$
So our base case holds. Now the difficulty would be to assume we have some arbitrary graph for which this formula holds, to then prove it holds for all graphs bigger than this. I cannot possibly construct all bigger graphs. I am guessing there is some different strategy in graph theory to induction proofs.
This result could also follow easily from the handshaking lemma if I assume that $n-1$ vertices have at most degree $n-2$. If someone has an alternative suggestion, please let me know.
graph-theory induction
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
I have just started my journey into the field of graph theory. I wish to show the following result:
Prove that for every disconnected graph $G = (V, E)$ it holds
$|E| leq frac{1}{2}
(|V| − 1)(|V | − 2)$.
I think the best way to tackle this, is via induction. I want to start with the smallest possible graph you can have, which would be on $2$ vertices, so $n=2$
We know that there are $0$ edges and thus:
$$|E|=0 leq frac{1}{2} (2-1)(2-2)=0. $$
So our base case holds. Now the difficulty would be to assume we have some arbitrary graph for which this formula holds, to then prove it holds for all graphs bigger than this. I cannot possibly construct all bigger graphs. I am guessing there is some different strategy in graph theory to induction proofs.
This result could also follow easily from the handshaking lemma if I assume that $n-1$ vertices have at most degree $n-2$. If someone has an alternative suggestion, please let me know.
graph-theory induction
graph-theory induction
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
edited yesterday
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
asked 2 days ago
WesleyGroupshaveFeelingsToo
821218
821218
In your base case, you meant (2-2) instead of (2-0) right?
– mathnoob
yesterday
yes indeed, you are correct.
– WesleyGroupshaveFeelingsToo
yesterday
add a comment |
In your base case, you meant (2-2) instead of (2-0) right?
– mathnoob
yesterday
yes indeed, you are correct.
– WesleyGroupshaveFeelingsToo
yesterday
In your base case, you meant (2-2) instead of (2-0) right?
– mathnoob
yesterday
In your base case, you meant (2-2) instead of (2-0) right?
– mathnoob
yesterday
yes indeed, you are correct.
– WesleyGroupshaveFeelingsToo
yesterday
yes indeed, you are correct.
– WesleyGroupshaveFeelingsToo
yesterday
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Hint: It might be easier to not use induction.
Suppose $G = (V,E)$ is a disconnected graph. Then, we can split $G$ into two disconnected subgraphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ with $|V_1| ge 1$, $|V_2| ge 1$.
Trivially, $|V| = |V_1|+|V_2|$ and $|E| = |E_1|+|E_2|$.
Also, $|E_1| le dbinom{|V_1|}{2}$ and $|E_2| le dbinom{|V_2|}{2} = dbinom{|V|-|V_1|}{2}$.
Can you use the above to show that $|E| = |E_1|+|E_2| le dbinom{|V|-1}{2}$?
answered 2 days ago
JimmyK4542
39.8k245105
By $binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices.
– WesleyGroupshaveFeelingsToo
2 days ago
add a comment |
up vote
1
down vote
Say part one has $x$ vertices and other $n-x$. Then we have at most $${xchoose 2}+{n-xchoose 2}$$ edges, which is clearly $$leq {n-1choose 2}$$
answered 2 days ago
greedoid
34.3k114488
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Hint: It might be easier to not use induction.
Suppose $G = (V,E)$ is a disconnected graph. Then, we can split $G$ into two disconnected subgraphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ with $|V_1| ge 1$, $|V_2| ge 1$.
Trivially, $|V| = |V_1|+|V_2|$ and $|E| = |E_1|+|E_2|$.
Also, $|E_1| le dbinom{|V_1|}{2}$ and $|E_2| le dbinom{|V_2|}{2} = dbinom{|V|-|V_1|}{2}$.
Can you use the above to show that $|E| = |E_1|+|E_2| le dbinom{|V|-1}{2}$?
answered 2 days ago
JimmyK4542
39.8k245105
By $binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices.
– WesleyGroupshaveFeelingsToo
2 days ago
add a comment |
up vote
1
down vote
accepted
Hint: It might be easier to not use induction.
Suppose $G = (V,E)$ is a disconnected graph. Then, we can split $G$ into two disconnected subgraphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ with $|V_1| ge 1$, $|V_2| ge 1$.
Trivially, $|V| = |V_1|+|V_2|$ and $|E| = |E_1|+|E_2|$.
Also, $|E_1| le dbinom{|V_1|}{2}$ and $|E_2| le dbinom{|V_2|}{2} = dbinom{|V|-|V_1|}{2}$.
Can you use the above to show that $|E| = |E_1|+|E_2| le dbinom{|V|-1}{2}$?
answered 2 days ago
JimmyK4542
39.8k245105
By $binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices.
– WesleyGroupshaveFeelingsToo
2 days ago
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Hint: It might be easier to not use induction.
Suppose $G = (V,E)$ is a disconnected graph. Then, we can split $G$ into two disconnected subgraphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ with $|V_1| ge 1$, $|V_2| ge 1$.
Trivially, $|V| = |V_1|+|V_2|$ and $|E| = |E_1|+|E_2|$.
Also, $|E_1| le dbinom{|V_1|}{2}$ and $|E_2| le dbinom{|V_2|}{2} = dbinom{|V|-|V_1|}{2}$.
Can you use the above to show that $|E| = |E_1|+|E_2| le dbinom{|V|-1}{2}$?
answered 2 days ago
JimmyK4542
39.8k245105
Hint: It might be easier to not use induction.
Suppose $G = (V,E)$ is a disconnected graph. Then, we can split $G$ into two disconnected subgraphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ with $|V_1| ge 1$, $|V_2| ge 1$.
Trivially, $|V| = |V_1|+|V_2|$ and $|E| = |E_1|+|E_2|$.
Also, $|E_1| le dbinom{|V_1|}{2}$ and $|E_2| le dbinom{|V_2|}{2} = dbinom{|V|-|V_1|}{2}$.
Can you use the above to show that $|E| = |E_1|+|E_2| le dbinom{|V|-1}{2}$?
answered 2 days ago
JimmyK4542
39.8k245105
answered 2 days ago
JimmyK4542
39.8k245105
answered 2 days ago
JimmyK4542
39.8k245105
answered 2 days ago
JimmyK4542
39.8k245105
39.8k245105
By $binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices.
– WesleyGroupshaveFeelingsToo
2 days ago
add a comment |
By $binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices.
– WesleyGroupshaveFeelingsToo
2 days ago
By $binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices.
– WesleyGroupshaveFeelingsToo
2 days ago
By $binom{|V_1|}{2}$ you probably mean the amount of ways we can form edges with the available vertices.
– WesleyGroupshaveFeelingsToo
2 days ago
add a comment |
up vote
1
down vote
Say part one has $x$ vertices and other $n-x$. Then we have at most $${xchoose 2}+{n-xchoose 2}$$ edges, which is clearly $$leq {n-1choose 2}$$
answered 2 days ago
greedoid
34.3k114488
add a comment |
up vote
1
down vote
Say part one has $x$ vertices and other $n-x$. Then we have at most $${xchoose 2}+{n-xchoose 2}$$ edges, which is clearly $$leq {n-1choose 2}$$
answered 2 days ago
greedoid
34.3k114488
add a comment |
up vote
1
down vote
up vote
1
down vote
Say part one has $x$ vertices and other $n-x$. Then we have at most $${xchoose 2}+{n-xchoose 2}$$ edges, which is clearly $$leq {n-1choose 2}$$
answered 2 days ago
greedoid
34.3k114488
Say part one has $x$ vertices and other $n-x$. Then we have at most $${xchoose 2}+{n-xchoose 2}$$ edges, which is clearly $$leq {n-1choose 2}$$
answered 2 days ago
greedoid
34.3k114488
answered 2 days ago
greedoid
34.3k114488
answered 2 days ago
greedoid
34.3k114488
answered 2 days ago
greedoid
34.3k114488
34.3k114488
add a comment |
add a comment |
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%2f3005377%2fprove-that-for-every-disconnected-graph-g-v-e-it-holds-e-leq-frac1%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
In your base case, you meant (2-2) instead of (2-0) right?
– mathnoob
yesterday
yes indeed, you are correct.
– WesleyGroupshaveFeelingsToo
yesterday