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.


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.