Some structural, metric and convex properties on the boundary of a graph

NEW

Problem: Let $G$ be a finite simple connected graph. For vertices $u,v$, say that $v$ is maximally distant from $u$ if

$$d(u,w)\le d(u,v)\quad\text{for every }w\in N(v).$$

The boundary is

$$\partial(G)=\{v:\text{ $v$ is maximally distant from some vertex $u$}\}.$$

The periphery is

$$\operatorname{Per}(G)=\{v:e(v)=\operatorname{diam}(G)\}.$$

A vertex is extreme if its open neighborhood is a clique, equivalently its closed neighborhood is geodesically convex/simplicial. The reconstructed conjecture is:

If $G$ has no extreme vertices and $|\partial(G)|=4$, then

$$\partial(G)=\operatorname{Per}(G).$$

Result: The conjecture is true.

Proof. First, $\operatorname{Per}(G)\subseteq \partial(G)$: if $d(x,y)=\operatorname{diam}(G)$, then every neighbor $z$ of $x$ satisfies $d(y,z)\le \operatorname{diam}(G)=d(y,x)$, so $x\in\partial(G)$, and similarly $y\in\partial(G)$.

We use two lemmas.

Lemma 1. If $v$ is not extreme, then $v$ lies on a shortest path between two boundary vertices distinct from $v$.

Indeed, since $v$ is not extreme, it has two nonadjacent neighbors $a,b$. Then $d(a,b)=2$, so $v\in I(a,b)$. Choose a pair $x,y\neq v$ with $v\in I(x,y)$ maximizing $d(x,y)$. If $x$ had a neighbor $x'$ with $d(x',y)>d(x,y)$, then necessarily $d(x',y)=d(x,y)+1$, and the triangle inequality gives

$$d(x',y)\le d(x',v)+d(v,y)\le d(x,v)+1+d(v,y)=d(x,y)+1.$$

Thus equality holds throughout, so $v\in I(x',y)$, contradicting maximality. Hence $x$ is maximally distant from $y$. Similarly $y$ is maximally distant from $x$. Therefore $x,y\in\partial(G)$.

Lemma 2. Let $S$ be a four-point metric space such that every point of $S$ lies between two of the other three. Then every point of $S$ has eccentricity equal to $\operatorname{diam}(S)$.

Let $S=\{a,b,c,d\}$, and suppose $a$ lies between $b,c$. Write $d(a,b)=x$, $d(a,c)=y$, so $d(b,c)=x+y$. Point $b$ cannot lie between $a,c$, and it also cannot lie between $c,d$; otherwise the required betweenness condition for $d$ becomes impossible by strict positivity of distances. Hence $b$ lies between $a,d$. Similarly $c$ lies between $a,d$. Therefore

$$d(a,d)=d(a,b)+d(b,d)=d(a,c)+d(c,d).$$

The point $d$ cannot lie between $a,b$ or $a,c$, so it lies between $b,c$:

$$d(b,c)=d(b,d)+d(c,d).$$

Solving these equations gives

$$d(a,d)=d(b,c)=x+y,$$

and the remaining four distances are $x$ or $y$. Thus the diameter is $x+y$, and each point is incident with a diameter pair.

Now apply Lemma 1 to each vertex of $\partial(G)$. Since $G$ has no extreme vertices and $|\partial(G)|=4$, every boundary vertex lies between two other boundary vertices. Hence Lemma 2 applies to the metric induced on $\partial(G)$, so every boundary vertex has distance equal to

$$\max\{d(p,q):p,q\in\partial(G)\}$$

from another boundary vertex.

But the graph diameter is realized by a pair of peripheral vertices, and peripheral vertices lie in $\partial(G)$. Therefore

$$\operatorname{diam}(G)=\max\{d(p,q):p,q\in\partial(G)\}.$$

So every $v\in\partial(G)$ has eccentricity $\operatorname{diam}(G)$, i.e. $v\in\operatorname{Per}(G)$. Since the reverse inclusion was already shown, $\partial(G)=\operatorname{Per}(G)$.

Citation: No external proof is invoked; this gives a complete resolution under the standard definitions used in the cited paper.