Algebraic proof involving Independent Set Problem & Maximum Degree
up vote
1
down vote
favorite
I was wondering if somebody could help me with a graph-related proof!
Let:
$G=(V,E)$ be an undirected graph;
$S subseteq V$ a maximal independent set;
$Delta$ the maximum degree of the graph ( = the maximum number of edges any vertex has).
I strongly suspect that $Delta geq frac{|S|}{|V setminus S|}$ for a certain category of graphs, like non-trivial connected graphs perhaps; however I'm struggling to prove it and yielded poor results so far.
What do you guys think, can this be (dis)proved?
proof-verification graph-theory algorithms
asked Nov 14 at 14:44
J. Brown
84
add a comment |
up vote
1
down vote
favorite
I was wondering if somebody could help me with a graph-related proof!
Let:
$G=(V,E)$ be an undirected graph;
$S subseteq V$ a maximal independent set;
$Delta$ the maximum degree of the graph ( = the maximum number of edges any vertex has).
I strongly suspect that $Delta geq frac{|S|}{|V setminus S|}$ for a certain category of graphs, like non-trivial connected graphs perhaps; however I'm struggling to prove it and yielded poor results so far.
What do you guys think, can this be (dis)proved?
proof-verification graph-theory algorithms
asked Nov 14 at 14:44
J. Brown
84
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I was wondering if somebody could help me with a graph-related proof!
Let:
$G=(V,E)$ be an undirected graph;
$S subseteq V$ a maximal independent set;
$Delta$ the maximum degree of the graph ( = the maximum number of edges any vertex has).
I strongly suspect that $Delta geq frac{|S|}{|V setminus S|}$ for a certain category of graphs, like non-trivial connected graphs perhaps; however I'm struggling to prove it and yielded poor results so far.
What do you guys think, can this be (dis)proved?
proof-verification graph-theory algorithms
asked Nov 14 at 14:44
J. Brown
84
I was wondering if somebody could help me with a graph-related proof!
Let:
$G=(V,E)$ be an undirected graph;
$S subseteq V$ a maximal independent set;
$Delta$ the maximum degree of the graph ( = the maximum number of edges any vertex has).
I strongly suspect that $Delta geq frac{|S|}{|V setminus S|}$ for a certain category of graphs, like non-trivial connected graphs perhaps; however I'm struggling to prove it and yielded poor results so far.
What do you guys think, can this be (dis)proved?
proof-verification graph-theory algorithms
proof-verification graph-theory algorithms
asked Nov 14 at 14:44
J. Brown
84
asked Nov 14 at 14:44
J. Brown
84
edited Nov 14 at 15:02
asked Nov 14 at 14:44
J. Brown
84
asked Nov 14 at 14:44
J. Brown
84
asked Nov 14 at 14:44
J. Brown
84
84
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
Yes, this is true for all connected graphs on more than $1$ vertex. (Or, for an even weaker assumption, all graphs with no isolated vertices.)
Let $S$ be a maximal independent set. Each vertex of $S$ must be adjacent to some vertex of $V setminus S$, since otherwise it wouldn't be connected to anything.
This gives us at least $|S|$ edges incident to $|Vsetminus S|$ vertices, so one of the vertices must be incident to at least $frac{|S|}{|Vsetminus S|}$ of them.
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
It took me a bit to visualize the last statement but I think I got it: would it be rightfully justified with the pigeonhole principle?
– J. Brown
Nov 14 at 15:20
That's the idea, yes.
– Misha Lavrov
Nov 14 at 15:39
Thanks very much Misha!
– J. Brown
Nov 14 at 15:46
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
Yes, this is true for all connected graphs on more than $1$ vertex. (Or, for an even weaker assumption, all graphs with no isolated vertices.)
Let $S$ be a maximal independent set. Each vertex of $S$ must be adjacent to some vertex of $V setminus S$, since otherwise it wouldn't be connected to anything.
This gives us at least $|S|$ edges incident to $|Vsetminus S|$ vertices, so one of the vertices must be incident to at least $frac{|S|}{|Vsetminus S|}$ of them.
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
It took me a bit to visualize the last statement but I think I got it: would it be rightfully justified with the pigeonhole principle?
– J. Brown
Nov 14 at 15:20
That's the idea, yes.
– Misha Lavrov
Nov 14 at 15:39
Thanks very much Misha!
– J. Brown
Nov 14 at 15:46
add a comment |
up vote
0
down vote
accepted
Yes, this is true for all connected graphs on more than $1$ vertex. (Or, for an even weaker assumption, all graphs with no isolated vertices.)
Let $S$ be a maximal independent set. Each vertex of $S$ must be adjacent to some vertex of $V setminus S$, since otherwise it wouldn't be connected to anything.
This gives us at least $|S|$ edges incident to $|Vsetminus S|$ vertices, so one of the vertices must be incident to at least $frac{|S|}{|Vsetminus S|}$ of them.
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
It took me a bit to visualize the last statement but I think I got it: would it be rightfully justified with the pigeonhole principle?
– J. Brown
Nov 14 at 15:20
That's the idea, yes.
– Misha Lavrov
Nov 14 at 15:39
Thanks very much Misha!
– J. Brown
Nov 14 at 15:46
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
Yes, this is true for all connected graphs on more than $1$ vertex. (Or, for an even weaker assumption, all graphs with no isolated vertices.)
Let $S$ be a maximal independent set. Each vertex of $S$ must be adjacent to some vertex of $V setminus S$, since otherwise it wouldn't be connected to anything.
This gives us at least $|S|$ edges incident to $|Vsetminus S|$ vertices, so one of the vertices must be incident to at least $frac{|S|}{|Vsetminus S|}$ of them.
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
Yes, this is true for all connected graphs on more than $1$ vertex. (Or, for an even weaker assumption, all graphs with no isolated vertices.)
Let $S$ be a maximal independent set. Each vertex of $S$ must be adjacent to some vertex of $V setminus S$, since otherwise it wouldn't be connected to anything.
This gives us at least $|S|$ edges incident to $|Vsetminus S|$ vertices, so one of the vertices must be incident to at least $frac{|S|}{|Vsetminus S|}$ of them.
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
answered Nov 14 at 15:06
Misha Lavrov
41.5k555101
41.5k555101
It took me a bit to visualize the last statement but I think I got it: would it be rightfully justified with the pigeonhole principle?
– J. Brown
Nov 14 at 15:20
That's the idea, yes.
– Misha Lavrov
Nov 14 at 15:39
Thanks very much Misha!
– J. Brown
Nov 14 at 15:46
add a comment |
It took me a bit to visualize the last statement but I think I got it: would it be rightfully justified with the pigeonhole principle?
– J. Brown
Nov 14 at 15:20
That's the idea, yes.
– Misha Lavrov
Nov 14 at 15:39
Thanks very much Misha!
– J. Brown
Nov 14 at 15:46
It took me a bit to visualize the last statement but I think I got it: would it be rightfully justified with the pigeonhole principle?
– J. Brown
Nov 14 at 15:20
It took me a bit to visualize the last statement but I think I got it: would it be rightfully justified with the pigeonhole principle?
– J. Brown
Nov 14 at 15:20
That's the idea, yes.
– Misha Lavrov
Nov 14 at 15:39
That's the idea, yes.
– Misha Lavrov
Nov 14 at 15:39
Thanks very much Misha!
– J. Brown
Nov 14 at 15:46
Thanks very much Misha!
– J. Brown
Nov 14 at 15:46
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%2f2998338%2falgebraic-proof-involving-independent-set-problem-maximum-degree%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
