Proof: If $G$ is connected and $rad(G) \leq k \leq diam(G)$, then there exists a vertex $v \in V(G)$ such that $e(v)=k$.

264 Views Asked by At

I believe e(v) mean the ecc(v) and ecc means eccentricity of a vertex in a graph, which is maximum distance that any vertex u is from vertex v. The proof seem trivial. I am confused what I am really proving because ecc(v)=k for all v will be between $rad(G) \leq k \leq diam(G)$, right?

Here is what I write:

Let G be a connected graph such that $rad(G) \leq k \leq diam(G)$. Further, let $u,v,c \in V(G)$ such that $d(u,v)=diam(G)$ and $rad(G)=ecc(c)$, or $c$ is in the center of G. For $ecc(u)=k $, $rad(G)=d(u,c) \leq ecc(u) \leq diam(G)$. Therefore, u is such a vertex. Therefore, there exists a vertex $v \in V(G)$ such that $ecc(v)=k$.

Is this answering the proof right?

1

There are 1 best solutions below

3
On BEST ANSWER

The problem is not asking you to prove the (trivial) statement that, if $k$ is the eccentricity of some vertex, then $k$ is a number between $\operatorname{rad}(G)$ and $\operatorname{diam}(G)$. Rather, it asks you to prove the (less trivial) converse statement: if $k$ is a number between $\operatorname{rad}(G)$ and $\operatorname{diam}(G)$, then $k$ is the degree of some vertex.

For example, if $G$ is a connected graph with $\operatorname{rad}(G)=42$ and $\operatorname{diam}(G)=79$, can you prove that there is a vertex $v$ with $\operatorname{ecc}(v)=61$?