# Construction of a graph with specific property.

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.

## 1 Answer

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.

• 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. – monalisa Mar 9 '16 at 4:25
• Right.... I got it now... thanks – monalisa Mar 9 '16 at 12:26