finding the minimal property of a graph While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs.
My question is what about the square of the cycles $C_n$? are they too minimal self-centered? I worked out on few examples. Somewhere it is and somewhere not. How to prove theoretically that squares of cycles $C_n$ are not minimal self-centered. 
A graph is said to be minimal if it loses its property if we remove any arbitrary edge.
 A: For each cycle $C_n$, we label the vertices clockwise $v_1, v_2, ..., v_n$, and denote $e_{i,j}$ as the edge connecting the vertices $v_i, v_j$. Let the square of cycle $C_n$ be the graph $S_n$, with the same naming for the vertices.
Assume to the contrary that the graph $S_n$ is minimally self-centered. Since it is self-centered, the graph diameter and graph radius must be both equal to some integer $k$. 
We first consider the case where $n\ge6$. For $n\ge6$, you can verify that $k\ge2$, since the $d(v_1, v_{\lfloor{n/2}\rfloor})\ge2$ 
Now, let us remove the edge $e_{1,2}$ between vertices $v_1, v_2$ to produce a graph $T_n$. 
Lemma 1: In the graph $T_n$, the graph distance $d(v_i,v_j)$ between any two vertices is the same as that in $S_n$ if and only if $(v_i,v_j)\neq(v_1,v_2)$, and $d(v_1,v_2)=2$. 
Proof: We can see this by noting that, if in $S_n$, the path of minimum length between $v_i, v_j$ passed through the edge $e_{1,2}$, then the path must include an edge $e_{a,1}$ or $e_{2,b}$ (or both), for otherwise the path is simply $e_{1,2}$ and must connect the vertices $v_1, v_2$.


*

*If the path contains the edge $e_{a,1}$, the edge must be $e_{n-1,1}$. (The path $e_{n,1}e_{1,2}$ cannot be part of any minimal path since $e_{n,2}$ would have been a shorter path. Edit: Also, as pointed out by @IvanLoh, the path $e_{3,1}e_{1,2}$ cannot be part of any minimal path since $e_{3,2}$ would have been a shorter path.) We can then change the segment of the path $e_{n-1,1}e_{1,2}$ to $e_{n-1,n}e_{n,2}$ with no change to the minimal path length.

*Similarly, if the path contains the edge $e_{2,b}$, the edge must be $e_{2,4}$. We can change the segment of the path $e_{1,2}e_{2,4}$ to $e_{1,3}e_{3,4}$.


By Lemma 1, since the graph distance between any two vertices other than $v_1,v_2$ remains the same, and $d(v_1,v_2)=2\le k$, the graph diameter and graph radius will not change either, and $T_n$ is also a self-centered graph, contradicting the assumption that $S_n$ is minimally self-centered.
It remains to check the cases where $n<6$, and this can be done easily by hand.
