1
$\begingroup$

Given $G$ a finite simple undirected graph and $n \geq 2$ a natural number, let $\mathcal{G}(G,n)$ denote the following game between players $A,B$:

Fix a countable set of vertices $\lbrace v_0, v_1,\ldots\rbrace$. Player $A$ moves first by selecting $n$ distinct vertices, and player $B$ responds by drawing an edge between two of them. Player $A$ wins if the graph $G$ is eventually drawn, and $B$ wins otherwise.

Question: Can $A$ always win $\mathcal{G}(G,n)$?

My own attempt: My first intuition told me to try a proof by induction on the number of edges in $G$: Suppose $G$ has $k+1$ edges, and suppose $G'$ is some subgraph of $G$ with one edge removed. By inductive hypothesis, suppose $A$ can force $G'$ to be drawn selecting at most $2N$ vertices throughout the game $\mathcal{G}(G',n)$. $A$ can then repeat this process to create $N$ copies of $G'$, with $a_1,b_1,\ldots a_N,b_N$ corresponding to the missing edge in $G$ in each copy. Now, if $A$ plays their same strategy on only those $2N$ vertices, we know that they can produce a copy of $G'$. But now we want that specifically one such edge $(a_i,b_i)$ be drawn (in order to complete one of the $G'$ copies to a $G$), and I don't see how this can be guaranteed.

I'm hoping that there's a basic combinatorial or graph-theoretic argument that answers this question, but my knowledge of either is too lacking to know where to look. Any assistance would be greatly appreciated.

edit: Just to clarify, $B$ may choose to draw the same edge over and over, when presented with the opportunity. Indeed, the game would be trivial otherwise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.