From trying out with small $n$, this is what I have: the configuration that gives the most number of vectors is an L-shaped configuration with "legs" of equal length. That is, points $(0,0)$ and $(1,0), (2,0), \dots,(n,0)$ and $(0,1) \dots (0,n)$. There are $2n^2+4n$ vectors. Of course there are other configurations that also gives this many vectors, namely their reflections and rotations, and also a T-shaped configuration. But for the purpose of the proof, I think we can do it with these steps: 1. Claim that the L-shaped configuration above gives the maximal number of vectors 2. Prove by induction. Suppose for $2k+1$ points we have L-shaped configuration as above, then we show that there are only several places where the next two points can go if we want to maintain connectivity. We can enumerate those cases and show that for $2k+3$ points, the optimal configuration is still $L$ shaped or some T-shaped, which still give the same number of vectors.

hendrata01 wrote: From trying out with small $n$, this is what I have: the configuration that gives the most number of vectors is an L-shaped configuration with "legs" of equal length. That is, points $(0,0)$ and $(1,0), (2,0), \dots,(n,0)$ and $(0,1) \dots (0,n)$. There are $2n^2+4n$ vectors. Of course there are other configurations that also gives this many vectors, namely their reflections and rotations, and also a T-shaped configuration. But for the purpose of the proof, I think we can do it with these steps: 1. Claim that the L-shaped configuration above gives the maximal number of vectors 2. Prove by induction. Suppose for $2k+1$ points we have L-shaped configuration as above, then we show that there are only several places where the next two points can go if we want to maintain connectivity. We can enumerate those cases and show that for $2k+3$ points, the optimal configuration is still $L$ shaped or some T-shaped, which still give the same number of vectors. You need to deal with several issues with a method like that. The two biggest are that you haven't given any indication as to why the optimal set for $2k+1$ points should contain the optimal set for $2k-1$ points and that you say yourself that there are multiple equality cases, but you've only dealt with one in your outline.

Answer is $2n^2+4n+1$ (there's also zero vector, but of course it's not worth any attention). It could be obtained by L-shaped configuration. But what is important is how many vectors are wasted. We claim that minimal number of those is $2n^2-2n$ (of course there's $(2n+1)2n+1=4n^2+2n+1$ vectors). Fix one point and recursively go to closest unvisited point. Most crucial observation is that if we at the moment went through vertical segment and previously we went through $v$ vertical segments, there's at least $2v$ new wasted vectors, same as with horizontal segments, because every pair of two unitary horizontal segments make parallelogram. In the end we went through $v$ vertical segments and $2n-v$ horizontal segments so we have $2(1+2+...+v + 1+2+...+(2n-v)) \geq 2n^2-2n$ wasted vectors.

Like others have said, the answer $2n^2+4n+1$ can be obtained with an L-like shape. Since the set of $2n+1$ points is connected, there is a spanning tree of $a$ horizontal segments and $b$ vertical segments, where $a+b=2n$. Thus, there set of $2n+1$ points is contained in a $(a+1)\times (b+1)$ grid. Any vector between two points in the grid is of the form $(x,y)$ where $|x|\le a$, $|y|\le b$, and $x$ and $y$ are of the same sign, where $0$ is of either sign. Thus, the maximal number of vectors is \[2(a+1)(b+1)-1\le 2(n+1)(n+1)-1=2n^2+4n+1\] Hence, $2n^2+4n+1$ is the maximal number of vectors. edit: fixed minor typo

(Note: in the following, I consider only vectors with a non-negative $y$-component). There must be at least $a$ horizontal unit segments and $b$ vertical unit segments, with $a+b=2n$. Notice that if we have two vertical unit segments, this produces two equal vectors (other than the aforementioned unit segments). If $v_1=...=v_x$ are vectors proven to be equal by this reasoning, then it is easy to see that $v_i$ and $v_j$ weren't proven to be equal for any $|i-j|>1$. Therefore, we have proven there are ${{a}\choose{2}}$ extra vectors. Similarly, we can prove that there are ${{b}\choose{2}}$ extra vectors, all distinct from the previous ones. By Karamata, there are ${{a}\choose{2}}+{{b}\choose{2}} \ge 2{{n}\choose{2}}=n^2-n$ extra vectors. By considering vectors with a negative $y$-coordinate, there are at least $2n^2-2n$ extra vectors. Hence, there are at most $(2n)(2n+1)-2n^2+2n=\boxed{2n^2+4n}$ vectors. (1 more if you consider null vector). For a configuration, take $(0,0);(1,0),...,(n,0),(n,1)...,(n,n)$. 200th post