A robot is placed on some vertex of a 3x3 grid. At each move the robot can take one step (up, down, left or right) along the edge of the grid to the adjacent vertex, but it cannot go outside the grid. The robot can revisit vertices, but it cannot revisit edges. What is the most number of edges that it can visit?
I think the highest number of edges you can visit is
21
Reasoning
Each of the eight vertices on the edge of the grid (not in corners) has degree three which means we can visit, at most, two of these vertices more than once (at the beginning and at the end). Hence, six of these vertices will have edges coming from them not included in the path. The minimum number of edges missed in a path will thus be three as we can pair up these six vertices as the endpoints of the missing edges.
Example
I number the vertices included in the path, together with highlighting the missed edges in red
I believe I have the solution for the general $n \times n$:
As user quarague indicated in the comments, this problem boils down to finding the least number of edges to remove such that the remaining graph has two odd-degree nodes. That subgraph has a Eulerian path - a path that uses all the remaining edges. All the interior nodes already have an even degree so we only need to deal with nodes around the border. This means that all the deletions can be around the border to obtain the optimal result.
For even $n \geq 4$:
We can use the following pattern of deleted edges (shown in red). The two odd-degree nodes are shown with circles - they will be the endpoints of the path. This gives $2n^2$ remaining edges.
For odd $n \geq 3$:
We can use the following pattern of deleted edges. This gives $2n^2+3$ remaining edges. This matches the solution found by hexomino for $n=3$.
For completeness, $n=2$ is a special case, which can be solved like so:
