Mixing
![Find area of quadrilateral in triangle. [closed]](https://lh4.googleusercontent.com/-xR1MvkJUIqE/AAAAAAAAAAI/AAAAAAAAAG4/T114cLYcRe8/s72-c/photo.jpg?sz=32)
If $alpha(Gsquare K_m)geq n(G)$, then $G$ is $m$-colorable.
Definitions:
$Gsquare K_m$: The Cartesian Product Graph of an arbitrary graph $G$, and the complete graph on $m$ vertices, $K_m$.
$alpha(Gsquare K_m)$: The size of a maximum independent set in the above graph.
$m$-colorable: The vertices of the graph can be partitioned into $m$ independent sets.
$n(G)$: The number of vertices in $G$. Also written as $n(G)=|V(G)|$.
This is actually one direction of an if and only if question, "A graph $G$ is $m$-colorable if and only if $alpha(Gsquare K_m)geq n(G)$."
For the forward direction, if we have a graph $G$ that is $m$-colorable, then then exists an independent set $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$. To see this, construct a subset of vertices from $V(Gsquare K_m)$ where we include the vertices from the independent set $S_i$ from the $i^{th}$ copy of $G$, also denoted $G_i$ for all $iin [m]$. This will produce an independent $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$.
However, I am having difficultly with the reverse direction. I feel as though the logical process would either be to use contrapositive or contradiction.
Here's my best attempt at contradiction.
Assume that $alpha(Gsquare K_m)geq n(G)$. We wish to show that $G$ is $m$-colorable. Suppose, on the contrary, that $G$ is not $m$-colorable. Thus, there is no way to partition $G$ into $m$ independent sets, so in some partition of $m$ sets of $V(G)$, there must exist two adjacent vertices in at least one of these $m$ sets.
Since $K_m$ is the complete graph on $m$ vertices, we can only include 1 vertex from each of the $n(G)$ copies of $K_m$ in $Gsquare K_m$ to an independent set. We have acknowledged above that $G$ cannot be partitioned into $m$ independent sets, so for any partition of $m$ sets on $V(G)$, at least two vertices must be adjacent. Thus, in the graph $Gsquare K_m$, we cannot include both of these vertices in any independent set, which implies that $alpha(Gsquare K_m)<n(G)$. This is a contradiction to our assumption that $alpha(Gsquare K_m)geq n(G)$, and thus $G$ is $m$-colorable.
My professor specialized in graph coloring. He insists that I use some form of a proper coloring on this graph, but for whatever reason I simply cannot wrap my head around this concept.
Any thoughts?
proof-verification graph-theory coloring
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
add a comment |
Definitions:
$Gsquare K_m$: The Cartesian Product Graph of an arbitrary graph $G$, and the complete graph on $m$ vertices, $K_m$.
$alpha(Gsquare K_m)$: The size of a maximum independent set in the above graph.
$m$-colorable: The vertices of the graph can be partitioned into $m$ independent sets.
$n(G)$: The number of vertices in $G$. Also written as $n(G)=|V(G)|$.
This is actually one direction of an if and only if question, "A graph $G$ is $m$-colorable if and only if $alpha(Gsquare K_m)geq n(G)$."
For the forward direction, if we have a graph $G$ that is $m$-colorable, then then exists an independent set $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$. To see this, construct a subset of vertices from $V(Gsquare K_m)$ where we include the vertices from the independent set $S_i$ from the $i^{th}$ copy of $G$, also denoted $G_i$ for all $iin [m]$. This will produce an independent $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$.
However, I am having difficultly with the reverse direction. I feel as though the logical process would either be to use contrapositive or contradiction.
Here's my best attempt at contradiction.
Assume that $alpha(Gsquare K_m)geq n(G)$. We wish to show that $G$ is $m$-colorable. Suppose, on the contrary, that $G$ is not $m$-colorable. Thus, there is no way to partition $G$ into $m$ independent sets, so in some partition of $m$ sets of $V(G)$, there must exist two adjacent vertices in at least one of these $m$ sets.
Since $K_m$ is the complete graph on $m$ vertices, we can only include 1 vertex from each of the $n(G)$ copies of $K_m$ in $Gsquare K_m$ to an independent set. We have acknowledged above that $G$ cannot be partitioned into $m$ independent sets, so for any partition of $m$ sets on $V(G)$, at least two vertices must be adjacent. Thus, in the graph $Gsquare K_m$, we cannot include both of these vertices in any independent set, which implies that $alpha(Gsquare K_m)<n(G)$. This is a contradiction to our assumption that $alpha(Gsquare K_m)geq n(G)$, and thus $G$ is $m$-colorable.
My professor specialized in graph coloring. He insists that I use some form of a proper coloring on this graph, but for whatever reason I simply cannot wrap my head around this concept.
Any thoughts?
proof-verification graph-theory coloring
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
Sorry what is $n(G)$?
– mathnoob
Nov 21 '18 at 23:50
$n(G)$ is the number of vertices in the graph $G$. This parameter is also described as $n(G)=|V(G)|$
– Steve Schroeder
Nov 22 '18 at 2:13
add a comment |
Definitions:
$Gsquare K_m$: The Cartesian Product Graph of an arbitrary graph $G$, and the complete graph on $m$ vertices, $K_m$.
$alpha(Gsquare K_m)$: The size of a maximum independent set in the above graph.
$m$-colorable: The vertices of the graph can be partitioned into $m$ independent sets.
$n(G)$: The number of vertices in $G$. Also written as $n(G)=|V(G)|$.
This is actually one direction of an if and only if question, "A graph $G$ is $m$-colorable if and only if $alpha(Gsquare K_m)geq n(G)$."
For the forward direction, if we have a graph $G$ that is $m$-colorable, then then exists an independent set $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$. To see this, construct a subset of vertices from $V(Gsquare K_m)$ where we include the vertices from the independent set $S_i$ from the $i^{th}$ copy of $G$, also denoted $G_i$ for all $iin [m]$. This will produce an independent $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$.
However, I am having difficultly with the reverse direction. I feel as though the logical process would either be to use contrapositive or contradiction.
Here's my best attempt at contradiction.
Assume that $alpha(Gsquare K_m)geq n(G)$. We wish to show that $G$ is $m$-colorable. Suppose, on the contrary, that $G$ is not $m$-colorable. Thus, there is no way to partition $G$ into $m$ independent sets, so in some partition of $m$ sets of $V(G)$, there must exist two adjacent vertices in at least one of these $m$ sets.
Since $K_m$ is the complete graph on $m$ vertices, we can only include 1 vertex from each of the $n(G)$ copies of $K_m$ in $Gsquare K_m$ to an independent set. We have acknowledged above that $G$ cannot be partitioned into $m$ independent sets, so for any partition of $m$ sets on $V(G)$, at least two vertices must be adjacent. Thus, in the graph $Gsquare K_m$, we cannot include both of these vertices in any independent set, which implies that $alpha(Gsquare K_m)<n(G)$. This is a contradiction to our assumption that $alpha(Gsquare K_m)geq n(G)$, and thus $G$ is $m$-colorable.
My professor specialized in graph coloring. He insists that I use some form of a proper coloring on this graph, but for whatever reason I simply cannot wrap my head around this concept.
Any thoughts?
proof-verification graph-theory coloring
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
Definitions:
$Gsquare K_m$: The Cartesian Product Graph of an arbitrary graph $G$, and the complete graph on $m$ vertices, $K_m$.
$alpha(Gsquare K_m)$: The size of a maximum independent set in the above graph.
$m$-colorable: The vertices of the graph can be partitioned into $m$ independent sets.
$n(G)$: The number of vertices in $G$. Also written as $n(G)=|V(G)|$.
This is actually one direction of an if and only if question, "A graph $G$ is $m$-colorable if and only if $alpha(Gsquare K_m)geq n(G)$."
For the forward direction, if we have a graph $G$ that is $m$-colorable, then then exists an independent set $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$. To see this, construct a subset of vertices from $V(Gsquare K_m)$ where we include the vertices from the independent set $S_i$ from the $i^{th}$ copy of $G$, also denoted $G_i$ for all $iin [m]$. This will produce an independent $Ssubset V(Gsquare K_m)$ such that $|S|=n(G)$.
However, I am having difficultly with the reverse direction. I feel as though the logical process would either be to use contrapositive or contradiction.
Here's my best attempt at contradiction.
Assume that $alpha(Gsquare K_m)geq n(G)$. We wish to show that $G$ is $m$-colorable. Suppose, on the contrary, that $G$ is not $m$-colorable. Thus, there is no way to partition $G$ into $m$ independent sets, so in some partition of $m$ sets of $V(G)$, there must exist two adjacent vertices in at least one of these $m$ sets.
Since $K_m$ is the complete graph on $m$ vertices, we can only include 1 vertex from each of the $n(G)$ copies of $K_m$ in $Gsquare K_m$ to an independent set. We have acknowledged above that $G$ cannot be partitioned into $m$ independent sets, so for any partition of $m$ sets on $V(G)$, at least two vertices must be adjacent. Thus, in the graph $Gsquare K_m$, we cannot include both of these vertices in any independent set, which implies that $alpha(Gsquare K_m)<n(G)$. This is a contradiction to our assumption that $alpha(Gsquare K_m)geq n(G)$, and thus $G$ is $m$-colorable.
My professor specialized in graph coloring. He insists that I use some form of a proper coloring on this graph, but for whatever reason I simply cannot wrap my head around this concept.
Any thoughts?
proof-verification graph-theory coloring
proof-verification graph-theory coloring
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
edited Nov 22 '18 at 2:15
Steve Schroeder
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
asked Nov 21 '18 at 18:22
Steve SchroederSteve Schroeder
1759
1759
Sorry what is $n(G)$?
– mathnoob
Nov 21 '18 at 23:50
$n(G)$ is the number of vertices in the graph $G$. This parameter is also described as $n(G)=|V(G)|$
– Steve Schroeder
Nov 22 '18 at 2:13
add a comment |
Sorry what is $n(G)$?
– mathnoob
Nov 21 '18 at 23:50
$n(G)$ is the number of vertices in the graph $G$. This parameter is also described as $n(G)=|V(G)|$
– Steve Schroeder
Nov 22 '18 at 2:13
Sorry what is $n(G)$?
– mathnoob
Nov 21 '18 at 23:50
Sorry what is $n(G)$?
– mathnoob
Nov 21 '18 at 23:50
$n(G)$ is the number of vertices in the graph $G$. This parameter is also described as $n(G)=|V(G)|$
– Steve Schroeder
Nov 22 '18 at 2:13
$n(G)$ is the number of vertices in the graph $G$. This parameter is also described as $n(G)=|V(G)|$
– Steve Schroeder
Nov 22 '18 at 2:13
add a comment |
0
active
oldest
votes
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%2f3008128%2fif-alphag-square-k-m-geq-ng-then-g-is-m-colorable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3008128%2fif-alphag-square-k-m-geq-ng-then-g-is-m-colorable%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
Sorry what is $n(G)$?
– mathnoob
Nov 21 '18 at 23:50
$n(G)$ is the number of vertices in the graph $G$. This parameter is also described as $n(G)=|V(G)|$
– Steve Schroeder
Nov 22 '18 at 2:13