Andrew and Ben play on graph












3














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!










share|cite|improve this question




















  • 1




    Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
    – Ross Millikan
    Apr 22 '18 at 17:04










  • Right before the game ends, the graph will be a union of disconnected star graphs.
    – vadim123
    Apr 22 '18 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 '18 at 17:05






  • 1




    @RossMillikan for $4$, Ben always wins...
    – Alicia S.
    Apr 22 '18 at 17:06






  • 1




    @AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
    – gt6989b
    Apr 22 '18 at 17:11
















3














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!










share|cite|improve this question




















  • 1




    Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
    – Ross Millikan
    Apr 22 '18 at 17:04










  • Right before the game ends, the graph will be a union of disconnected star graphs.
    – vadim123
    Apr 22 '18 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 '18 at 17:05






  • 1




    @RossMillikan for $4$, Ben always wins...
    – Alicia S.
    Apr 22 '18 at 17:06






  • 1




    @AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
    – gt6989b
    Apr 22 '18 at 17:11














3












3








3


3





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!










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 27 '18 at 18:23









Larry B.

2,776728




2,776728










asked Apr 22 '18 at 16:57









Alicia S.Alicia S.

162




162








  • 1




    Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
    – Ross Millikan
    Apr 22 '18 at 17:04










  • Right before the game ends, the graph will be a union of disconnected star graphs.
    – vadim123
    Apr 22 '18 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 '18 at 17:05






  • 1




    @RossMillikan for $4$, Ben always wins...
    – Alicia S.
    Apr 22 '18 at 17:06






  • 1




    @AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
    – gt6989b
    Apr 22 '18 at 17:11














  • 1




    Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
    – Ross Millikan
    Apr 22 '18 at 17:04










  • Right before the game ends, the graph will be a union of disconnected star graphs.
    – vadim123
    Apr 22 '18 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 '18 at 17:05






  • 1




    @RossMillikan for $4$, Ben always wins...
    – Alicia S.
    Apr 22 '18 at 17:06






  • 1




    @AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
    – gt6989b
    Apr 22 '18 at 17:11








1




1




Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 '18 at 17:04




Have you tried some small cases? Ben wins $2$, Andrew wins $3$. What about $4$?
– Ross Millikan
Apr 22 '18 at 17:04












Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 '18 at 17:05




Right before the game ends, the graph will be a union of disconnected star graphs.
– vadim123
Apr 22 '18 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 '18 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 '18 at 17:05




1




1




@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 '18 at 17:06




@RossMillikan for $4$, Ben always wins...
– Alicia S.
Apr 22 '18 at 17:06




1




1




@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 '18 at 17:11




@AliciaS. paths cannot be since you can take out the middle edge... vadim is correct
– gt6989b
Apr 22 '18 at 17:11










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
});


}
});














draft saved

draft discarded


















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

























0






active

oldest

votes








0






active

oldest

votes









active

oldest

votes






active

oldest

votes
















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Plaza Victoria

Puebla de Zaragoza

Musa