Prove Vizing Class 1 if maximum degree vertices induce forest by induction
up vote
1
down vote
favorite
I tried to prove that if for a simple graph $G$, vertices of maximum degree induce a forest, then $chi'(G) leq Delta(G)$, in other words, the graph is in Vizing Class 1.
When I applied induction on $|E(G)|$, I encountered the problem, that if there is only one vertex $v in V(G)$ having maximum degree, I cannot ensure that I can apply the induction hypothesis on $Gsetminus e$ for an edge $e$ incident with $v$.
If I remove $e$, there might be vertices of degree $Delta(G) - 1$ inducing a cycle.
How can I solve this problem? Is there a way to fix this proof?
graph-theory
asked 23 hours ago
Lydia
62
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
favorite
I tried to prove that if for a simple graph $G$, vertices of maximum degree induce a forest, then $chi'(G) leq Delta(G)$, in other words, the graph is in Vizing Class 1.
When I applied induction on $|E(G)|$, I encountered the problem, that if there is only one vertex $v in V(G)$ having maximum degree, I cannot ensure that I can apply the induction hypothesis on $Gsetminus e$ for an edge $e$ incident with $v$.
If I remove $e$, there might be vertices of degree $Delta(G) - 1$ inducing a cycle.
How can I solve this problem? Is there a way to fix this proof?
graph-theory
asked 23 hours ago
Lydia
62
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Check this math.stackexchange.com/questions/1009600/…
– hbm
14 hours ago
i tried to do the same, but i think there is a problem there. I can't apply the induction hypothesis, because $v$ might be the only vertex having maximum degree
– Lydia
12 hours ago
the proof still applies. In the case of only one vertex, just remove any edge incident with it.
– hbm
12 hours ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I tried to prove that if for a simple graph $G$, vertices of maximum degree induce a forest, then $chi'(G) leq Delta(G)$, in other words, the graph is in Vizing Class 1.
When I applied induction on $|E(G)|$, I encountered the problem, that if there is only one vertex $v in V(G)$ having maximum degree, I cannot ensure that I can apply the induction hypothesis on $Gsetminus e$ for an edge $e$ incident with $v$.
If I remove $e$, there might be vertices of degree $Delta(G) - 1$ inducing a cycle.
How can I solve this problem? Is there a way to fix this proof?
graph-theory
asked 23 hours ago
Lydia
62
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I tried to prove that if for a simple graph $G$, vertices of maximum degree induce a forest, then $chi'(G) leq Delta(G)$, in other words, the graph is in Vizing Class 1.
When I applied induction on $|E(G)|$, I encountered the problem, that if there is only one vertex $v in V(G)$ having maximum degree, I cannot ensure that I can apply the induction hypothesis on $Gsetminus e$ for an edge $e$ incident with $v$.
If I remove $e$, there might be vertices of degree $Delta(G) - 1$ inducing a cycle.
How can I solve this problem? Is there a way to fix this proof?
graph-theory
graph-theory
asked 23 hours ago
Lydia
62
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 23 hours ago
Lydia
62
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 23 hours ago
Lydia
62
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 23 hours ago
Lydia
62
asked 23 hours ago
Lydia
62
62
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Lydia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Check this math.stackexchange.com/questions/1009600/…
– hbm
14 hours ago
i tried to do the same, but i think there is a problem there. I can't apply the induction hypothesis, because $v$ might be the only vertex having maximum degree
– Lydia
12 hours ago
the proof still applies. In the case of only one vertex, just remove any edge incident with it.
– hbm
12 hours ago
add a comment |
Check this math.stackexchange.com/questions/1009600/…
– hbm
14 hours ago
i tried to do the same, but i think there is a problem there. I can't apply the induction hypothesis, because $v$ might be the only vertex having maximum degree
– Lydia
12 hours ago
the proof still applies. In the case of only one vertex, just remove any edge incident with it.
– hbm
12 hours ago
Check this math.stackexchange.com/questions/1009600/…
– hbm
14 hours ago
Check this math.stackexchange.com/questions/1009600/…
– hbm
14 hours ago
i tried to do the same, but i think there is a problem there. I can't apply the induction hypothesis, because $v$ might be the only vertex having maximum degree
– Lydia
12 hours ago
i tried to do the same, but i think there is a problem there. I can't apply the induction hypothesis, because $v$ might be the only vertex having maximum degree
– Lydia
12 hours ago
the proof still applies. In the case of only one vertex, just remove any edge incident with it.
– hbm
12 hours ago
the proof still applies. In the case of only one vertex, just remove any edge incident with it.
– hbm
12 hours ago
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Lydia is a new contributor. Be nice, and check out our Code of Conduct.
Lydia is a new contributor. Be nice, and check out our Code of Conduct.
Lydia is a new contributor. Be nice, and check out our Code of Conduct.
Lydia is a new contributor. Be nice, and check out our Code of Conduct.
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
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2995381%2fprove-vizing-class-1-if-maximum-degree-vertices-induce-forest-by-induction%23new-answer', 'question_page');
}
);
Post as a guest
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
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
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
Check this math.stackexchange.com/questions/1009600/…
– hbm
14 hours ago
i tried to do the same, but i think there is a problem there. I can't apply the induction hypothesis, because $v$ might be the only vertex having maximum degree
– Lydia
12 hours ago
the proof still applies. In the case of only one vertex, just remove any edge incident with it.
– hbm
12 hours ago