A bipartite graph $G$ such that for any partition $X$ and $Y$, $alpha(G)> max {X,Y}$
$begingroup$
The question is
Construct a bipartite graph $G$ such that for any partition $X$ and $Y$, $alpha(G)> max {X,Y}$. Explain.
I did this graph:
Here it works, $alpha (G) =9$ (marked in blue box), and each partition is $7$. However, if we flip the red circled vertices so that the $3$ top vertices become in $Y$-partition $Y$ will be equal to $9$, which violates what I want to prove. Is there any way to fix my graph?
proof-verification graph-theory
edited Dec 10 '18 at 13:48
Saad
19.7k92352
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
$endgroup$
add a comment |
$begingroup$
The question is
Construct a bipartite graph $G$ such that for any partition $X$ and $Y$, $alpha(G)> max {X,Y}$. Explain.
I did this graph:
Here it works, $alpha (G) =9$ (marked in blue box), and each partition is $7$. However, if we flip the red circled vertices so that the $3$ top vertices become in $Y$-partition $Y$ will be equal to $9$, which violates what I want to prove. Is there any way to fix my graph?
proof-verification graph-theory
edited Dec 10 '18 at 13:48
Saad
19.7k92352
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
$endgroup$
$begingroup$
Can you please tell me what $alpha(G)$ is?
$endgroup$
– user614671
Dec 10 '18 at 18:14
add a comment |
$begingroup$
The question is
Construct a bipartite graph $G$ such that for any partition $X$ and $Y$, $alpha(G)> max {X,Y}$. Explain.
I did this graph:
Here it works, $alpha (G) =9$ (marked in blue box), and each partition is $7$. However, if we flip the red circled vertices so that the $3$ top vertices become in $Y$-partition $Y$ will be equal to $9$, which violates what I want to prove. Is there any way to fix my graph?
proof-verification graph-theory
edited Dec 10 '18 at 13:48
Saad
19.7k92352
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
$endgroup$
The question is
Construct a bipartite graph $G$ such that for any partition $X$ and $Y$, $alpha(G)> max {X,Y}$. Explain.
I did this graph:
Here it works, $alpha (G) =9$ (marked in blue box), and each partition is $7$. However, if we flip the red circled vertices so that the $3$ top vertices become in $Y$-partition $Y$ will be equal to $9$, which violates what I want to prove. Is there any way to fix my graph?
proof-verification graph-theory
proof-verification graph-theory
edited Dec 10 '18 at 13:48
Saad
19.7k92352
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
edited Dec 10 '18 at 13:48
Saad
19.7k92352
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
edited Dec 10 '18 at 13:48
Saad
19.7k92352
edited Dec 10 '18 at 13:48
Saad
19.7k92352
edited Dec 10 '18 at 13:48
Saad
19.7k92352
19.7k92352
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
asked Dec 10 '18 at 11:39
Fatmaelzahraa ElsheimyFatmaelzahraa Elsheimy
162
162
$begingroup$
Can you please tell me what $alpha(G)$ is?
$endgroup$
– user614671
Dec 10 '18 at 18:14
add a comment |
$begingroup$
Can you please tell me what $alpha(G)$ is?
$endgroup$
– user614671
Dec 10 '18 at 18:14
$begingroup$
Can you please tell me what $alpha(G)$ is?
$endgroup$
– user614671
Dec 10 '18 at 18:14
$begingroup$
Can you please tell me what $alpha(G)$ is?
$endgroup$
– user614671
Dec 10 '18 at 18:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
When you flip the graph then y will have cardinality 9 and maximal independant set will become 9 .
So it proves what you are trying to prove.
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
$endgroup$
1
$begingroup$
But we want strict greater, not greater or equals.
$endgroup$
– nafhgood
Dec 10 '18 at 16:17
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%2f3033804%2fa-bipartite-graph-g-such-that-for-any-partition-x-and-y-alphag-max%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$
When you flip the graph then y will have cardinality 9 and maximal independant set will become 9 .
So it proves what you are trying to prove.
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
$endgroup$
1
$begingroup$
But we want strict greater, not greater or equals.
$endgroup$
– nafhgood
Dec 10 '18 at 16:17
add a comment |
$begingroup$
When you flip the graph then y will have cardinality 9 and maximal independant set will become 9 .
So it proves what you are trying to prove.
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
$endgroup$
1
$begingroup$
But we want strict greater, not greater or equals.
$endgroup$
– nafhgood
Dec 10 '18 at 16:17
add a comment |
$begingroup$
When you flip the graph then y will have cardinality 9 and maximal independant set will become 9 .
So it proves what you are trying to prove.
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
$endgroup$
When you flip the graph then y will have cardinality 9 and maximal independant set will become 9 .
So it proves what you are trying to prove.
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
answered Dec 10 '18 at 15:41
Saurabh DangeSaurabh Dange
11
11
1
$begingroup$
But we want strict greater, not greater or equals.
$endgroup$
– nafhgood
Dec 10 '18 at 16:17
add a comment |
1
$begingroup$
But we want strict greater, not greater or equals.
$endgroup$
– nafhgood
Dec 10 '18 at 16:17
1
1
$begingroup$
But we want strict greater, not greater or equals.
$endgroup$
– nafhgood
Dec 10 '18 at 16:17
$begingroup$
But we want strict greater, not greater or equals.
$endgroup$
– nafhgood
Dec 10 '18 at 16:17
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%2f3033804%2fa-bipartite-graph-g-such-that-for-any-partition-x-and-y-alphag-max%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$
Can you please tell me what $alpha(G)$ is?
$endgroup$
– user614671
Dec 10 '18 at 18:14