I am trying to find out graphs where eccentricity of every vertex is one except two vertices. And the eccentricity of these two vertices is two. I came to the conclusion that a path graph $P_3$ and a complete graph minus an edge, i.e., $K_n-e$, for $n\geq3$, are such graphs.

Is there any other graph with the given property? Kindly help. Thanks for the efforts.


There are no other graphs with this property, other than the complete graphs with one edge removed. Even $P_3$ is just $K_3$ with an edge removed.

Consider a graph $G = (V = \{x_1, x_2, y_1, y_2, \dots y_{n-2}\}, E)$ where $\epsilon(x_i) = 2$ and $\epsilon(y_i) = 1$.

For each $y_i$, $(y_i, v) \in E$ for all $v \in V \setminus \{y_i\}$.

For each $x_i$, there exists $v \neq x_i$ such that $(x_i, v) \not \in E$. For those $v$, we know that $\epsilon(v) > 1$. The only valid $v$ are $x_1$ and $x_2$. Therefore, the edges $(x_1, x_2)$ and $(x_2, x_1)$ must be excluded. In an undirected graph, this is a single edge.

In the construction of this graph, we've included every possible edge between pairs of vertices except for a single one, which is between the vertices with eccentricity $2$. There are $\binom n 2$ such $n$-vertex undirected graphs with this property.

  • $\begingroup$ Thanks for the explanation. So you mean to say for $n=3$, there are 3 such graphs...but I think $P_3$ is the only graph... So, you must have included isomorphic graphs in your answer. Am I right? Pardon me, if I am not. $\endgroup$ – monalisa Mar 9 '16 at 4:25
  • $\begingroup$ Right.... I got it now... thanks $\endgroup$ – monalisa Mar 9 '16 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.