maximum number of edges to be removed to possess a property I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all vertices. And if we delete 3 edges incident on a single vertex, it loses its property that eccentricity is same for all vertices, because eccentricity is not same for those graphs having a vertex of degree1. How to find out the maximum number of edges to be deleted so that eccentricity is still same.  Any idea or suggestion will be helpful. Thanks for your help.
 A: Here is what I can say with certainty

Let $n\ge 5$.  The maximum number of edges that can be removed from a squared cycle so that the eccentricity of each vertex remains unchanged is at least $n-2-(n+2)\operatorname{mod}4$.

To show this is true, I will give an explicit set of removed edges in each case.  Label consecutive vertices of the cycle $1,2,3,\ldots, n$ and call an edge 'outer' if it connects adjacent vertices in the cycle, and 'inner' if it connects vertices a distance of two from each other.  Splitting into four cases, depending on the residue class of $n$ modulo $4$, we can remove the following edges:


*

*$n\equiv 0\operatorname{mod}4$: $n-6$ outer edges and $2$ inner edges.  Remove all outer edges except those connecting $(1,2),(2,3),(3,4),(\frac{n}{2}+1,\frac{n}{2}+2),(\frac{n}{2}+2,\frac{n}{2}+3),$ and $(\frac{n}{2}+3,\frac{n}{2}+4)$.  Remove inner edges connecting $(1,3)$ and $(\frac{n}{2}+2,\frac{n}{2}+4).$

*$n\equiv 1\operatorname{mod}4$: $n-5$ outer edges and $0$ inner edges.  Remove all outer edges except those connecting $(1,2),(2,3),(3,4),(\frac{n+3}{2},\frac{n+3}{2}+1),$ and $(\frac{n+3}{2}+1,\frac{n+3}{2}+2)$.  Remove no inner edges.

*$n\equiv 2\operatorname{mod}4$: $n-4$ outer edges and $2$ inner edges.  Remove all outer edges except those connecting $(1,2),(2,3),(\frac{n}{2}+1,\frac{n}{2}+2),$ and $(\frac{n}{2}+2,\frac{n}{2}+3)$.  Remove inner edges connecting $(1,3)$ and $(\frac{n}{2}+1,\frac{n}{2}+3)$.

*$n\equiv 3\operatorname{mod}4$: $n-5$ outer edges and $2$ inner edges.  Remove all outer edges except those connecting $(1,2),(2,3),(3,4),(\frac{n+3}{2},\frac{n+3}{2}+1),$ and $(\frac{n+3}{2}+1,\frac{n+3}{2}+2)$.  Remove inner edges connecting $(1,3)$ and $(\frac{n+3}{2},\frac{n+3}{2}+2)$.


This should all match up with the conjecture.  The above is proved case-by-case by induction.  Notice that the remaining graphs in all cases have two gaps of outer edges.  In each gap, we can add $2$ vertices and $2$ edges so that the eccentricity of each vertex is raised by $1$ (note that the eccentricity of a squared cycle with $n+4$ edges is $1$ greater than the eccentricity of a squared cycle with $n$ edges).
The hard part is getting rid of the words 'at least' in the above claim.  It can be shown that when $n\equiv 1\operatorname{mod}4$, we cannot remove any inner edges, and we need at least $5$ outer edges to preserve eccentricity.  This establishes the result for $n\equiv 1\operatorname{mod}4$.
When $n\equiv 0\operatorname{mod}4$, we can remove at most $2$ inner edges, but I can't seem to show that $6$ outer edges are necessary.
The other cases are even trickier.  I have reason to believe my result is true for all cases, but a formal proof eludes me.
