Abstract : A circuit in a simple undirected graph G=(V,E) is a sequence of vertices {v_1,v_2,...,v_{k+1}} such that v_1=v_{k+1} and {v_i,v_{i+1}} \in E for i=1,...,k. A circuit C is said to be edge-simple if no edge of G is used twice in C. In this article we study the following problem: which is the largest integer k such that, given any subset of k ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the k vertices in the prescribed order? We prove that k=10. To this end, we first provide a counterexample implying that k<11. To show that k>=10, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an ILP solver.
