Show that: $chi(G) + chi(overline{G}) leq |V| + 1$
$begingroup$
Show that: $chi(G) + chi(overline{G}) leq |V| + 1$
I have problem with starting with this task. I have already done similar ones like for example $chi(G) * chi(overline{G}) geq |V|$, but I can't really find the proper way of thinking to solve the task mentioned at the beginning.
Any tips?
discrete-mathematics graph-theory coloring
edited Jan 11 at 14:02
EdOverflow
25519
asked Jan 11 at 14:00
James SmithJames Smith
34817
$endgroup$
add a comment |
$begingroup$
Show that: $chi(G) + chi(overline{G}) leq |V| + 1$
I have problem with starting with this task. I have already done similar ones like for example $chi(G) * chi(overline{G}) geq |V|$, but I can't really find the proper way of thinking to solve the task mentioned at the beginning.
Any tips?
discrete-mathematics graph-theory coloring
edited Jan 11 at 14:02
EdOverflow
25519
asked Jan 11 at 14:00
James SmithJames Smith
34817
$endgroup$
$begingroup$
Have you tried induction on the number of vertices?
$endgroup$
– bof
Jan 11 at 14:03
$begingroup$
Not yet. Don't really know how to use it in this case as I haven't seen usage of induction in tasks of this type, but I will try to check if I will be to figure out something with it. Thanks.
$endgroup$
– James Smith
Jan 11 at 14:12
add a comment |
$begingroup$
Show that: $chi(G) + chi(overline{G}) leq |V| + 1$
I have problem with starting with this task. I have already done similar ones like for example $chi(G) * chi(overline{G}) geq |V|$, but I can't really find the proper way of thinking to solve the task mentioned at the beginning.
Any tips?
discrete-mathematics graph-theory coloring
edited Jan 11 at 14:02
EdOverflow
25519
asked Jan 11 at 14:00
James SmithJames Smith
34817
$endgroup$
Show that: $chi(G) + chi(overline{G}) leq |V| + 1$
I have problem with starting with this task. I have already done similar ones like for example $chi(G) * chi(overline{G}) geq |V|$, but I can't really find the proper way of thinking to solve the task mentioned at the beginning.
Any tips?
discrete-mathematics graph-theory coloring
discrete-mathematics graph-theory coloring
edited Jan 11 at 14:02
EdOverflow
25519
asked Jan 11 at 14:00
James SmithJames Smith
34817
edited Jan 11 at 14:02
EdOverflow
25519
asked Jan 11 at 14:00
James SmithJames Smith
34817
edited Jan 11 at 14:02
EdOverflow
25519
edited Jan 11 at 14:02
EdOverflow
25519
edited Jan 11 at 14:02
EdOverflow
25519
25519
asked Jan 11 at 14:00
James SmithJames Smith
34817
asked Jan 11 at 14:00
James SmithJames Smith
34817
asked Jan 11 at 14:00
James SmithJames Smith
34817
34817
$begingroup$
Have you tried induction on the number of vertices?
$endgroup$
– bof
Jan 11 at 14:03
$begingroup$
Not yet. Don't really know how to use it in this case as I haven't seen usage of induction in tasks of this type, but I will try to check if I will be to figure out something with it. Thanks.
$endgroup$
– James Smith
Jan 11 at 14:12
add a comment |
$begingroup$
Have you tried induction on the number of vertices?
$endgroup$
– bof
Jan 11 at 14:03
$begingroup$
Not yet. Don't really know how to use it in this case as I haven't seen usage of induction in tasks of this type, but I will try to check if I will be to figure out something with it. Thanks.
$endgroup$
– James Smith
Jan 11 at 14:12
$begingroup$
Have you tried induction on the number of vertices?
$endgroup$
– bof
Jan 11 at 14:03
$begingroup$
Have you tried induction on the number of vertices?
$endgroup$
– bof
Jan 11 at 14:03
$begingroup$
Not yet. Don't really know how to use it in this case as I haven't seen usage of induction in tasks of this type, but I will try to check if I will be to figure out something with it. Thanks.
$endgroup$
– James Smith
Jan 11 at 14:12
$begingroup$
Not yet. Don't really know how to use it in this case as I haven't seen usage of induction in tasks of this type, but I will try to check if I will be to figure out something with it. Thanks.
$endgroup$
– James Smith
Jan 11 at 14:12
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint. This can be proved by induction on $n(G)$, the number of vertices.
Choose any vertex $v$ of $G$. By the inductive hypothesis we have:
$$chi(G-v)+chi(overline{G-v})le n(G-v)+1=n(G)tag1$$
and we also have
$$chi(G)lechi(G-v)+1tag2$$
and
$$chi(overline G)lechi(overline{G-v})+1tag3$$
whence
$$chi(G)+chi(overline G)le n(G)+2.tag4$$
All we have to do now is show that equality can't hold in $(4)$. Well, for equality to hold in $(4)$, we must have equality in $(1)$, $(2)$, and $(3)$. But then . . .
Further hint:
Equality in $(2)$ implies $deg_G(v)gechi(G-v)$
answered Jan 11 at 14:28
bofbof
52.6k559121
$endgroup$
$begingroup$
Emm... A lot of time has passed since I asked that question, but was trying to focus on other classes. So if we would like to have equality in (2) then $deg(v) = Delta(G)$ or am I wrong? In that case it would not be possible to have equality in (3), right?
$endgroup$
– James Smith
Jan 22 at 19:18
1
$begingroup$
As I said in my Further hint, equality in $(2)$ implies $deg_G(v)gechi(G-v)$. If all the inequalities are equalities, then we have $$n(G)-1=deg_G(v)+deg_{overline G}(v)gechi(G-v)+chi(overline{G-v})=n(G),$$ i.e., $n(G)-1ge n(G)$, a contradiction.
$endgroup$
– bof
Jan 23 at 0: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%2f3069854%2fshow-that-chig-chi-overlineg-leq-v-1%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$
Hint. This can be proved by induction on $n(G)$, the number of vertices.
Choose any vertex $v$ of $G$. By the inductive hypothesis we have:
$$chi(G-v)+chi(overline{G-v})le n(G-v)+1=n(G)tag1$$
and we also have
$$chi(G)lechi(G-v)+1tag2$$
and
$$chi(overline G)lechi(overline{G-v})+1tag3$$
whence
$$chi(G)+chi(overline G)le n(G)+2.tag4$$
All we have to do now is show that equality can't hold in $(4)$. Well, for equality to hold in $(4)$, we must have equality in $(1)$, $(2)$, and $(3)$. But then . . .
Further hint:
Equality in $(2)$ implies $deg_G(v)gechi(G-v)$
answered Jan 11 at 14:28
bofbof
52.6k559121
$endgroup$
$begingroup$
Emm... A lot of time has passed since I asked that question, but was trying to focus on other classes. So if we would like to have equality in (2) then $deg(v) = Delta(G)$ or am I wrong? In that case it would not be possible to have equality in (3), right?
$endgroup$
– James Smith
Jan 22 at 19:18
1
$begingroup$
As I said in my Further hint, equality in $(2)$ implies $deg_G(v)gechi(G-v)$. If all the inequalities are equalities, then we have $$n(G)-1=deg_G(v)+deg_{overline G}(v)gechi(G-v)+chi(overline{G-v})=n(G),$$ i.e., $n(G)-1ge n(G)$, a contradiction.
$endgroup$
– bof
Jan 23 at 0:40
add a comment |
$begingroup$
Hint. This can be proved by induction on $n(G)$, the number of vertices.
Choose any vertex $v$ of $G$. By the inductive hypothesis we have:
$$chi(G-v)+chi(overline{G-v})le n(G-v)+1=n(G)tag1$$
and we also have
$$chi(G)lechi(G-v)+1tag2$$
and
$$chi(overline G)lechi(overline{G-v})+1tag3$$
whence
$$chi(G)+chi(overline G)le n(G)+2.tag4$$
All we have to do now is show that equality can't hold in $(4)$. Well, for equality to hold in $(4)$, we must have equality in $(1)$, $(2)$, and $(3)$. But then . . .
Further hint:
Equality in $(2)$ implies $deg_G(v)gechi(G-v)$
answered Jan 11 at 14:28
bofbof
52.6k559121
$endgroup$
$begingroup$
Emm... A lot of time has passed since I asked that question, but was trying to focus on other classes. So if we would like to have equality in (2) then $deg(v) = Delta(G)$ or am I wrong? In that case it would not be possible to have equality in (3), right?
$endgroup$
– James Smith
Jan 22 at 19:18
1
$begingroup$
As I said in my Further hint, equality in $(2)$ implies $deg_G(v)gechi(G-v)$. If all the inequalities are equalities, then we have $$n(G)-1=deg_G(v)+deg_{overline G}(v)gechi(G-v)+chi(overline{G-v})=n(G),$$ i.e., $n(G)-1ge n(G)$, a contradiction.
$endgroup$
– bof
Jan 23 at 0:40
add a comment |
$begingroup$
Hint. This can be proved by induction on $n(G)$, the number of vertices.
Choose any vertex $v$ of $G$. By the inductive hypothesis we have:
$$chi(G-v)+chi(overline{G-v})le n(G-v)+1=n(G)tag1$$
and we also have
$$chi(G)lechi(G-v)+1tag2$$
and
$$chi(overline G)lechi(overline{G-v})+1tag3$$
whence
$$chi(G)+chi(overline G)le n(G)+2.tag4$$
All we have to do now is show that equality can't hold in $(4)$. Well, for equality to hold in $(4)$, we must have equality in $(1)$, $(2)$, and $(3)$. But then . . .
Further hint:
Equality in $(2)$ implies $deg_G(v)gechi(G-v)$
answered Jan 11 at 14:28
bofbof
52.6k559121
$endgroup$
Hint. This can be proved by induction on $n(G)$, the number of vertices.
Choose any vertex $v$ of $G$. By the inductive hypothesis we have:
$$chi(G-v)+chi(overline{G-v})le n(G-v)+1=n(G)tag1$$
and we also have
$$chi(G)lechi(G-v)+1tag2$$
and
$$chi(overline G)lechi(overline{G-v})+1tag3$$
whence
$$chi(G)+chi(overline G)le n(G)+2.tag4$$
All we have to do now is show that equality can't hold in $(4)$. Well, for equality to hold in $(4)$, we must have equality in $(1)$, $(2)$, and $(3)$. But then . . .
Further hint:
Equality in $(2)$ implies $deg_G(v)gechi(G-v)$
answered Jan 11 at 14:28
bofbof
52.6k559121
edited Jan 12 at 6:54
answered Jan 11 at 14:28
bofbof
52.6k559121
answered Jan 11 at 14:28
bofbof
52.6k559121
answered Jan 11 at 14:28
bofbof
52.6k559121
52.6k559121
$begingroup$
Emm... A lot of time has passed since I asked that question, but was trying to focus on other classes. So if we would like to have equality in (2) then $deg(v) = Delta(G)$ or am I wrong? In that case it would not be possible to have equality in (3), right?
$endgroup$
– James Smith
Jan 22 at 19:18
1
$begingroup$
As I said in my Further hint, equality in $(2)$ implies $deg_G(v)gechi(G-v)$. If all the inequalities are equalities, then we have $$n(G)-1=deg_G(v)+deg_{overline G}(v)gechi(G-v)+chi(overline{G-v})=n(G),$$ i.e., $n(G)-1ge n(G)$, a contradiction.
$endgroup$
– bof
Jan 23 at 0:40
add a comment |
$begingroup$
Emm... A lot of time has passed since I asked that question, but was trying to focus on other classes. So if we would like to have equality in (2) then $deg(v) = Delta(G)$ or am I wrong? In that case it would not be possible to have equality in (3), right?
$endgroup$
– James Smith
Jan 22 at 19:18
1
$begingroup$
As I said in my Further hint, equality in $(2)$ implies $deg_G(v)gechi(G-v)$. If all the inequalities are equalities, then we have $$n(G)-1=deg_G(v)+deg_{overline G}(v)gechi(G-v)+chi(overline{G-v})=n(G),$$ i.e., $n(G)-1ge n(G)$, a contradiction.
$endgroup$
– bof
Jan 23 at 0:40
$begingroup$
Emm... A lot of time has passed since I asked that question, but was trying to focus on other classes. So if we would like to have equality in (2) then $deg(v) = Delta(G)$ or am I wrong? In that case it would not be possible to have equality in (3), right?
$endgroup$
– James Smith
Jan 22 at 19:18
$begingroup$
Emm... A lot of time has passed since I asked that question, but was trying to focus on other classes. So if we would like to have equality in (2) then $deg(v) = Delta(G)$ or am I wrong? In that case it would not be possible to have equality in (3), right?
$endgroup$
– James Smith
Jan 22 at 19:18
1
1
$begingroup$
As I said in my Further hint, equality in $(2)$ implies $deg_G(v)gechi(G-v)$. If all the inequalities are equalities, then we have $$n(G)-1=deg_G(v)+deg_{overline G}(v)gechi(G-v)+chi(overline{G-v})=n(G),$$ i.e., $n(G)-1ge n(G)$, a contradiction.
$endgroup$
– bof
Jan 23 at 0:40
$begingroup$
As I said in my Further hint, equality in $(2)$ implies $deg_G(v)gechi(G-v)$. If all the inequalities are equalities, then we have $$n(G)-1=deg_G(v)+deg_{overline G}(v)gechi(G-v)+chi(overline{G-v})=n(G),$$ i.e., $n(G)-1ge n(G)$, a contradiction.
$endgroup$
– bof
Jan 23 at 0: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%2f3069854%2fshow-that-chig-chi-overlineg-leq-v-1%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
$begingroup$
Have you tried induction on the number of vertices?
$endgroup$
– bof
Jan 11 at 14:03
$begingroup$
Not yet. Don't really know how to use it in this case as I haven't seen usage of induction in tasks of this type, but I will try to check if I will be to figure out something with it. Thanks.
$endgroup$
– James Smith
Jan 11 at 14:12