Prove, that graph $G$ has at least $chi(G)(chi(G)-1)/2$ edges.
up vote
3
down vote
favorite
Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $chi(G)(chi(G)-1)/2$? $chi(G)$ is the minimal number of colors we need to use to color the graph (it's chromatic index in other words).
I tried induction but I'm stuck at an induction step.
I do the induction on the number of edges.
When $|E(G)|=0$ then obviously we can color the graph using only one color, so the theorem holds.
Now induction step from $n Rightarrow n+1$ edges.
Let's erase any edge $e={v,u}$ from $G$. Then $chi(G-e)$ is either the same, or $chi(G-e)<chi(G)$, because we relaxed the graph an $v$ and $u$ no longer need to have different colors. From the first case the thesis is clear, because $G-e$ has more then $chi(G)(chi(G)-1)/2$ edges so with the one we erased it's still more. But from the second case we only know that $G geq chi'(G)(chi'(G)-1)/2$ and $chi'(G)(chi'(G)-1)/2 leq chi(G)(chi(G)-1)/2$ so that gives me nothing...
graph-theory coloring
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
add a comment |
up vote
3
down vote
favorite
Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $chi(G)(chi(G)-1)/2$? $chi(G)$ is the minimal number of colors we need to use to color the graph (it's chromatic index in other words).
I tried induction but I'm stuck at an induction step.
I do the induction on the number of edges.
When $|E(G)|=0$ then obviously we can color the graph using only one color, so the theorem holds.
Now induction step from $n Rightarrow n+1$ edges.
Let's erase any edge $e={v,u}$ from $G$. Then $chi(G-e)$ is either the same, or $chi(G-e)<chi(G)$, because we relaxed the graph an $v$ and $u$ no longer need to have different colors. From the first case the thesis is clear, because $G-e$ has more then $chi(G)(chi(G)-1)/2$ edges so with the one we erased it's still more. But from the second case we only know that $G geq chi'(G)(chi'(G)-1)/2$ and $chi'(G)(chi'(G)-1)/2 leq chi(G)(chi(G)-1)/2$ so that gives me nothing...
graph-theory coloring
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $chi(G)(chi(G)-1)/2$? $chi(G)$ is the minimal number of colors we need to use to color the graph (it's chromatic index in other words).
I tried induction but I'm stuck at an induction step.
I do the induction on the number of edges.
When $|E(G)|=0$ then obviously we can color the graph using only one color, so the theorem holds.
Now induction step from $n Rightarrow n+1$ edges.
Let's erase any edge $e={v,u}$ from $G$. Then $chi(G-e)$ is either the same, or $chi(G-e)<chi(G)$, because we relaxed the graph an $v$ and $u$ no longer need to have different colors. From the first case the thesis is clear, because $G-e$ has more then $chi(G)(chi(G)-1)/2$ edges so with the one we erased it's still more. But from the second case we only know that $G geq chi'(G)(chi'(G)-1)/2$ and $chi'(G)(chi'(G)-1)/2 leq chi(G)(chi(G)-1)/2$ so that gives me nothing...
graph-theory coloring
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $chi(G)(chi(G)-1)/2$? $chi(G)$ is the minimal number of colors we need to use to color the graph (it's chromatic index in other words).
I tried induction but I'm stuck at an induction step.
I do the induction on the number of edges.
When $|E(G)|=0$ then obviously we can color the graph using only one color, so the theorem holds.
Now induction step from $n Rightarrow n+1$ edges.
Let's erase any edge $e={v,u}$ from $G$. Then $chi(G-e)$ is either the same, or $chi(G-e)<chi(G)$, because we relaxed the graph an $v$ and $u$ no longer need to have different colors. From the first case the thesis is clear, because $G-e$ has more then $chi(G)(chi(G)-1)/2$ edges so with the one we erased it's still more. But from the second case we only know that $G geq chi'(G)(chi'(G)-1)/2$ and $chi'(G)(chi'(G)-1)/2 leq chi(G)(chi(G)-1)/2$ so that gives me nothing...
graph-theory coloring
graph-theory coloring
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
asked Jan 20 '14 at 19:22
Arek Krawczyk
1,10811020
1,10811020
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
9
down vote
accepted
Given a coloring of $G$ with $chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P
– Arek Krawczyk
Jan 20 '14 at 19:49
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%2f645339%2fprove-that-graph-g-has-at-least-chig-chig-1-2-edges%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
up vote
9
down vote
accepted
Given a coloring of $G$ with $chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P
– Arek Krawczyk
Jan 20 '14 at 19:49
add a comment |
up vote
9
down vote
accepted
Given a coloring of $G$ with $chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P
– Arek Krawczyk
Jan 20 '14 at 19:49
add a comment |
up vote
9
down vote
accepted
up vote
9
down vote
accepted
Given a coloring of $G$ with $chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
Given a coloring of $G$ with $chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
edited Jan 20 '14 at 19:33
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
answered Jan 20 '14 at 19:31
Zur Luria
1,115510
1,115510
Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P
– Arek Krawczyk
Jan 20 '14 at 19:49
add a comment |
Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P
– Arek Krawczyk
Jan 20 '14 at 19:49
Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P
– Arek Krawczyk
Jan 20 '14 at 19:49
Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P
– Arek Krawczyk
Jan 20 '14 at 19:49
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f645339%2fprove-that-graph-g-has-at-least-chig-chig-1-2-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
