Metric dimesnion Metric dimension of a graph $G$ can be defined as the minimal cardinality of the subsets $A\subseteq V(G)$ with the following property;
For any two vertices $u$ and $v$, we are able to find a vertex $a\in A$ such that $d(v,a)\neq d(u,a)$.
For instance, one may see that the metric dimension of the complete graph $K_n$ is $n-1$.
Now my question is:
How can I prove that an upper bound for the dimension of $G$ is at most |V(G)|-d(G), where the diameter of $G$ is denoted by $d(G)$?
 A: You need to show that there is an $A$ of size $|V(G)|-d(G)$ with the given property.
The fact that $G$ has diameter $d(G)$ means that there is a path of length $d(G)$ that is a shortest path between any of the $d(G)+1$ vertices in it. Can you use such a path to construct an appropriate $A$?
(Hint. you can ignore choices of $u,v$ where one or both of them are in $A$. They always work; just let $a$ be one of $u$ and $v$. So effectively you can "prevent" a vertex from being chosen as $u$ or $v$ by putting it into $A$).
A: Let $G$ be a graph on $n$ vertices and let $D$ denote the diameter of the graph. We want to show that the graph has a resolving set $A$ of cardinality at most $n-D$.  Because the diameter is $D$, there exist two vertices $x,y$ which are at distance $D$. Let  $x=v_0,v_1,\ldots,v_D=y$ be a shortest path in the graph from $x$ to $y$.  
Take $A$ to be the set $V - \{v_1,\ldots,v_D\}$.  We prove that any two distinct vertices $u, v \in V$ can be resolved by some vertex $a$ in $A$.  If at least one of $u,v$ is in $A$, say $u \in A$, then $u$ resolves $u$ and $v$.  If both $u, v \notin A$, then $u=v_i$ and $v=v_j$ for some $i, j \in \{1,\ldots,D\}$ with $i \ne j$.  In this case, the end-vertex $v_0 \in A$ of the path resolves the two vertices $u$ and $v$ on the path.
