Andrew and Ben play on graph
Given complete graph with $n$ vertices. Andrew in his turn removes exactly one edge and Ben in his turn removes two or three edges. They take turns one after another and Andrew begins. The player loses if the graph is disconnected after his turn. For what $n$ does Ben win and what's his winning strategy? For what $n$ does Andrew win?
Thank you for any hints or solutions!
combinatorics graph-theory game-theory combinatorial-game-theory
edited Nov 27 at 18:23
Larry B.
2,726727
asked Apr 22 at 16:57
Alicia S.
162
|
show 4 more comments
Given complete graph with $n$ vertices. Andrew in his turn removes exactly one edge and Ben in his turn removes two or three edges. They take turns one after another and Andrew begins. The player loses if the graph is disconnected after his turn. For what $n$ does Ben win and what's his winning strategy? For what $n$ does Andrew win?
Thank you for any hints or solutions!
combinatorics graph-theory game-theory combinatorial-game-theory
edited Nov 27 at 18:23
Larry B.
2,726727
asked Apr 22 at 16:57
Alicia S.
162
1
Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 at 17:04
Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 at 17:05
1
@SeanRoberson I don't really know any game theory lemmas/methods, thus I only tried some basic strategies - non of which led to the solution. PS. don't worry, after edit Ben is all right ;)
– Alicia S.
Apr 22 at 17:05
1
@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 at 17:06
1
@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 at 17:11
|
show 4 more comments
Given complete graph with $n$ vertices. Andrew in his turn removes exactly one edge and Ben in his turn removes two or three edges. They take turns one after another and Andrew begins. The player loses if the graph is disconnected after his turn. For what $n$ does Ben win and what's his winning strategy? For what $n$ does Andrew win?
Thank you for any hints or solutions!
combinatorics graph-theory game-theory combinatorial-game-theory
edited Nov 27 at 18:23
Larry B.
2,726727
asked Apr 22 at 16:57
Alicia S.
162
Given complete graph with $n$ vertices. Andrew in his turn removes exactly one edge and Ben in his turn removes two or three edges. They take turns one after another and Andrew begins. The player loses if the graph is disconnected after his turn. For what $n$ does Ben win and what's his winning strategy? For what $n$ does Andrew win?
Thank you for any hints or solutions!
combinatorics graph-theory game-theory combinatorial-game-theory
combinatorics graph-theory game-theory combinatorial-game-theory
edited Nov 27 at 18:23
Larry B.
2,726727
asked Apr 22 at 16:57
Alicia S.
162
edited Nov 27 at 18:23
Larry B.
2,726727
asked Apr 22 at 16:57
Alicia S.
162
edited Nov 27 at 18:23
Larry B.
2,726727
edited Nov 27 at 18:23
Larry B.
2,726727
edited Nov 27 at 18:23
Larry B.
2,726727
2,726727
asked Apr 22 at 16:57
Alicia S.
162
asked Apr 22 at 16:57
Alicia S.
162
asked Apr 22 at 16:57
Alicia S.
162
162
1
Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 at 17:04
Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 at 17:05
1
@SeanRoberson I don't really know any game theory lemmas/methods, thus I only tried some basic strategies - non of which led to the solution. PS. don't worry, after edit Ben is all right ;)
– Alicia S.
Apr 22 at 17:05
1
@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 at 17:06
1
@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 at 17:11
|
show 4 more comments
1
Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 at 17:04
Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 at 17:05
1
@SeanRoberson I don't really know any game theory lemmas/methods, thus I only tried some basic strategies - non of which led to the solution. PS. don't worry, after edit Ben is all right ;)
– Alicia S.
Apr 22 at 17:05
1
@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 at 17:06
1
@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 at 17:11
1
1
Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 at 17:04
Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 at 17:04
Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 at 17:05
Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 at 17:05
1
1
@SeanRoberson I don't really know any game theory lemmas/methods, thus I only tried some basic strategies - non of which led to the solution. PS. don't worry, after edit Ben is all right ;)
– Alicia S.
Apr 22 at 17:05
@SeanRoberson I don't really know any game theory lemmas/methods, thus I only tried some basic strategies - non of which led to the solution. PS. don't worry, after edit Ben is all right ;)
– Alicia S.
Apr 22 at 17:05
1
1
@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 at 17:06
@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 at 17:06
1
1
@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 at 17:11
@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 at 17:11
|
show 4 more comments
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%2f2749009%2fandrew-and-ben-play-on-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
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%2f2749009%2fandrew-and-ben-play-on-graph%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
1
Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 at 17:04
Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 at 17:05
1
@SeanRoberson I don't really know any game theory lemmas/methods, thus I only tried some basic strategies - non of which led to the solution. PS. don't worry, after edit Ben is all right ;)
– Alicia S.
Apr 22 at 17:05
1
@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 at 17:06
1
@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 at 17:11