I was trying to construct the graphs $G$ and $H$ by using the cycle graph $C_9$ (or $C_n$) and $H$ and $G$ are induced in $C_n$.
Graph $G$ is formed by attaching a vertex $x$ to $C_9$ (or $C_n\geq 7$) and by making it adjacent to vertex $1$ and all the vertices $j$, where $3\leq j\leq 8$ (or $3\leq j\leq n-1$). Here, in $G$, vertices $1$ and $x$ have eccentricity two and rest of the vertices have eccentricity three, shown in the following figure.
Similarly, I want to draw a graph $H$, where exactly two vertices have eccentricity three and rest of the vertices have eccentricity four.
The graph $H$ must be formed by appending exactly one vertex to $C_n$.
Kindly help.
Any hint will be of great help.
P.S. The construction for graph $G$ is for all cycles for $n\geq9$.
Best Answer
It's impossible for larger cycles ($n\ge 10$) as well.
Suppose that the center vertex $x$ has eccentricity $4$. Then there is a vertex $v$ at distance $4$ from $x$. Let $w$ be the vertex opposite from $v$ along the cycle (or one such vertex, when $n$ is odd). Then $d(v,w) > 4$: $v$ cannot reach $w$ in $4$ or fewer steps by going along the cycle (it is too far), but $v$ cannot reach $w$ in $4$ or fewer steps by going through $x$ (it takes $4$ steps just to get to $x$).
Therefore $x$ has eccentricity $3$. There must be a vertex at distance $3$ from $x$, and this can happen in two ways:
In case 1, in order for $v_3$ to have eccentricity at most $4$, every vertex which is $5$ or more steps from $v_3$ along the cycle must be adjacent to $x$. (That way, there is a length-$4$ path from $v_3$ to such a vertex by going through $x$.) We get a graph that contains at least the following edges:
(There don't need to be exactly three vertices opposite $v_3$ which we join to $x$, but there is at least one.)
But now, both $v_1$ and $v_5$ can already reach every other vertex in at most $3$ steps, and that (together with $x$) is too many vertices of eccentricity $3$.
A similar thing happens in case 2: we have to join $x$ to every vertex that's 5 or more steps away from either $v_3$ and $v_4$, and then $v_1$ and $v_6$ have eccentricity $3$ as well as $x$.