# On the Connectivity and Diameter of Geodetic Graphs

Asaf Etgar  The Hebrew University of Jerusalem  Nati Linial Supported in part
by grant 659/18 of the Israel Science Foundation The Hebrew University of
Jerusalem

###### Abstract

A graph $G$ is _geodetic_ if between any two vertices there exists a unique
shortest path. In 1962 Ore raised the challenge to characterize geodetic
graphs, but despite many attempts, such characterization still seems well
beyond reach. We may assume, of course, that $G$ is $2$-connected, and here we
consider only graphs with no vertices of degree $1$ or $2$. We prove that all
such graphs are, in fact $3$-connected. We also construct an infinite family
of such graphs of the largest known diameter, namely $5$.

##  1 Introduction

In this work we consider loopless, undirected graphs $G=(V,E)$. We think of a
path in $G$ as a sequence of vertices $P=(v_{1},\ldots v_{k})$, and the
subpath of $P$ from $v_{j}$ to $v_{l}$ is denoted $P(v_{j},v_{l})$. The length
of a path $P$ is denoted $|P|$, and path concatenation is denoted by $*$. The
distance between $u$ and $v$ is $d_{G}(v,u)=d(v,u)$, and is the length of a
shortest $u,v$ path. For clarity, we occasionally add an index indicating the
graph in which some parameter or quantity is calculated.

The notion of geodetic graphs was introduced by Ore [6] as a natural extension
of trees: a tree is a graph in which between any two vertices there exists a
unique simple path, and hence a unique shortest path (i.e - a geodesic). Ore
purposed an extended definition, and asked in which simple graphs geodesics
are unique. Some simple examples are trees, complete graphs, and odd-length
cycles. Specifically, Ore raised the challenge to characterize geodetic
graphs. Despite many attempts, a complete characterization still seems beyond
reach.

There are easy necessary and sufficient properties for a graph to be geodetic,
the following can be easily proved:

######  Claim 1.1.

A graph $G$ is not geodetic if and only if it contains an even circuit $C$
with two vertices $u,v\in C$ such that $d_{C}(u,v)=d_{G}(u,v)=\frac{|C|}{2}$.

######  Claim 1.2.

A graph $G$ is geodetic if and only if each block of $G$ is geodetic.

Here a _block_ is a maximal $2$-connected component of $G$. There is clearly
no loss in generality if we restrict our attention to $2$-connected graphs. By
1.2, since a vertex of degree $1$ is a block, it suffices to assume all
vertices have degree no less than $2$. Moreover, the following claim is given
in [12]:

######  Claim 1.3.

Let $G$ be a geodetic graph, and let $P=v_{1},\ldots,v_{k}$ be a path with
$\deg(v_{1}),\deg(v_{k})\geq 3$ and $\forall i\neq 1,k\;\deg(v_{i})=2$. Then
$P$ is the $v_{1},v_{k}$ geodesic.

By this claim, one can replace any path that consists of degree $2$ vertices
by a single weighted edge. Therefore the question of geodeticity gains a more
arithmetic flvaour. Since our emphasis is combinatorial and geometric we will
concentrate on graphs whose smallest degree is at least $3$.

There are not many families of geodetic graphs that are classified in full.
The only constructive classifications known presently are planar geodetic
graphs [12], which is extended to a classification of geodetic graphs
homeomorphic to a complete graph [11]. There is a considerable body of work
classifying geodetic graphs of diameter $2$ [10, 8, 1], including a
classification of such graphs. While some constructions are known, we do not
know that they exhaust all possible geodetic graphs of diameter $2$. In this
sense, the classification is lacking. Naturally - the question turns to higher
diameters. Some properties of geodetic graphs of diameter $3$ are known [7].
However, to the best of our knowledge the following is unknown:

######  Problem 1.

Do there exist geodetic blocks $G$ of diameter $3$ with $\delta(G)\geq 3$?

Here $\delta(G)$ is the minimal degree of $G$. Progress on this problem has
been very slow. Bridgland [2] constructed a family of geodetic blocks of
diameter $4$ and arbitrarily large minimal degree. This construction was later
generalized in several ways using block designs [9], yielding a family of
geodetic blocks of diameter $5$. This construction has the largest diameter
presently known. Despite many attempts, we were unable to retrieve the latter
paper. We therefore present these constructions along a different proof of
their geodeticity. A main problem that we raise is:

######  Problem 2.

What is the largest possible diameter of a geodetic block with minimal degree
$\geq 3$? Can it be arbitrarily large?

In the journey to classification, other properties of geodetic graphs were
discovered. A graph is called _self centered_ if its diameter equals its
radius. Geodetic blocks of diameter $2$ are known to have this property [10].
Likewise, for blocks of diameter $3$ [7]. Some connections to other graph
properties were explored, namely by Zelinka [15], Gorovoy and Zamiaikou [4],
and connections to other fields such as algebra and group theory [3, 5]. We
continue these lines of research, resulting in our main theorem:

######  Theorem 1.1.

Every $2$-connected geodetic graph $G$ with $\delta(G)\geq 3$ must be
$3$-connected. This lower bound is tight as shown by the Petersen Graph.

##  2 Geodetic Graphs and Connectivity

In this section we prove 1.1. From here on we assume $G$ is geodetic with
$\delta(G)\geq 3$. We denote the (unique) $v,u$ geodesic in $G$ by $\pi(v,u)$,
and by convention we enumerate its vertices in order from $v$ to $u$. Arguing
by contradiction, let $S=\\{x,y\\}$ be a vertex cut for which $d(x,y)$ is as
small as possible, denote this distance by $\ell$. We denote by $\Pi=\pi(x,y)$
the $x,y$ geodesic, with vertices $\Pi=x,x_{1},x_{2},\ldots,x_{\ell-1},y$. Let
$A_{1}\ldots A_{k}$ the connected components of $G\setminus S$. Clearly,
$x_{1},x_{2},\ldots,x_{\ell-1}$ all belong to the same connected component of
$G\setminus S$, say they are in $A_{1}$.

######  Lemma 2.1.

For every $i$, if $u,v\in A_{i}$, then $\pi_{G}(u,v)$ is contained in
$A_{i}\cup\Pi$.

###### Proof.

If $\pi_{G}(u,v)$ is not contained in $A_{i}\cup\Pi$, then it must leave
$A_{i}$ and come back. But the only way to exit $A_{i}$ is via $x$ or $y$. But
then $\pi_{G}(u,v)=\pi_{G}(u,x)*\Pi*\pi_{G}(y,v)$, since $\Pi$ is the $x,y$
geodesic. Thus $\pi_{G}(u,v)$ is contained in $A_{i}\cup\Pi$, as claimed. ∎

######  Lemma 2.2.

The graph $G\setminus S$ has exactly two connected components, i.e., $k=2$.

###### Proof.

Suppose toward contradiction that $A_{1},A_{2},A_{3}\neq\emptyset$. Let
$\pi_{i}$ to be an $x,y$ geodesic in the subgraph induced by $A_{i}\cup S$.
(in particular $\pi_{1}=\Pi$). At least two of the integers
$|\pi_{1}|,|\pi_{2}|,|\pi_{3}|$ have the same parity, so the corresponding
paths form a cycle $C$ of even length. We consider two cases:

  1. 1.

$C=\pi_{1}*\pi_{2}^{-1}$: Since
$\left|\pi_{2}\right|\geq\left|\pi_{1}\right|+2$ we can find two vertices
$v_{0},v_{1}\in A_{2}$ which are antipodal points on $C$. However,
$\pi_{2}(v_{0},v_{1})=\pi_{G}(v_{0},v_{1})$ by 2.1. But
$\pi_{C}(v_{0},x)*\Pi*\pi_{C}(y,v_{1})$ is another $v_{0},v_{1}$ path of the
same length, contradicting geodeticity.

  2. 2.

$C=\pi_{2}*\pi_{3}^{-1}$: Let $v_{0},v_{1}$ be $C$ \- antipodal points with
$v_{0}\in A_{2},v_{1}\in A_{3}$. The two arcs of $C$ that $v_{0},v_{1}$ define
are two $v_{0},v_{1}$ paths of equal length. By assumption $G$ is geodetic so
$\pi_{G}(v_{0},v_{1})$ differs from both these paths. But
$\pi_{G}(v_{0},v_{1})$ must traverse either $x$ or $y$. This means e.g., that
$|\pi_{G}(v_{0},x)|<|\pi_{2}(v_{0},x)|$ contrary to the assumption that
$\pi_{2}$ is a shortest $x,y$ path in $A_{2}\cup S$.

∎

A _graph contraction_ between two graphs $\Gamma,\Omega$, is a function
$f:V(\Gamma)\to V(\Omega)$ such that for any $vu\in E(\Gamma)$, either
$f(v)f(u)\in E(\Omega)$ or $f(v)=f(u)$. Clearly, for any $u,v\in V(\Gamma)$ it
holds that $d_{\Omega}(f(v),f(u))\leq d_{\Gamma}(v,u)$. Therefore if $\Gamma$
is connected, so is $f[\Gamma]$.

Let $\mathbb{Z}^{2}_{\infty}$ be the graph with vertex set $\mathbb{Z}^{2}$
where $p,q\in\mathbb{Z}^{2}$ are neighbors whenever
$\left\|p-q\right\|_{\infty}=1$. We denote coordinates in this plane by
$(\xi,\eta)$ and employ this graph as a visualization tool for $G$. This is
accomplished using the mapping $\varphi:V(G)\to\mathbb{Z}^{2}$, where

$\displaystyle\varphi(v)=\begin{cases}(d(x,v),d(y,v))&v\in A_{1}\cup S\\\
(-d(y,v)+\ell,-d(x,v)+\ell)&v\in A_{2}\cup S\end{cases}$

(Recall that $\ell=d(x,y)$). We denote the image of $G$ in
$\mathbb{Z}^{2}_{\infty}$ by $\Omega=\varphi[G]$. Clearly $\varphi$ is a graph
contraction, and therefore $\varphi[A_{i}]$ is a connected subgraph of
$\Omega$. For any $j$ define

$R_{j}=\left\\{v\in A_{1}\mid d(v,y)-d(v,x)=j\right\\}\qquad
L_{j}=\left\\{v\in A_{2}\mid d(v,y)-d(v,x)=j\right\\}$

For ease of notation, we add $x$ to $R_{\ell},L_{\ell}$ and $y$ to
$R_{-\ell}$, $L_{-\ell}$. We denote $R=\bigcup_{j=-\ell}^{\ell}R_{j}$ and
$L=\bigcup_{j=-\ell}^{\ell}L_{j}$. By 2.2 $G=R\cup L$, and
$\varphi[L_{j}],\varphi[R_{j}]$ are included in the straight line
$\\{(\xi,\xi+j)|\xi\in\mathbb{Z}\\}$.

Figure 1: How $\varphi$ maps a $2$-connected graph. $\Pi=(x,x_{1},y)$ are the
black vertices, $R_{1}$’s vertices are the gray square vertices and $L_{-1}$
is the white square vertex.

In using $\varphi(G)$ as a visualization tool, we keep in mind that $\varphi$
is not injective. We note that $\varphi[\Pi]$ is the interval between
$(0,\ell)$ and $(\ell,0)$, and that by geodeticity $\varphi^{-1}((j,\ell-j))$
is the $j$-th vertex in $\Pi$. In drawing $\varphi[R]$ and $\varphi[L]$, we
note that $\varphi[R]$ is “to the right” of $\varphi[\Pi]$, and $\varphi[L]$
is “to the left” of $\varphi[\Pi]$.

######  Lemma 2.3.

If $u,v$ are neighbors in $G$, $u\in R_{j},v\in R_{k}$, then
$\left|k-j\right|\leq 2$. Moreover, if $\left|k-j\right|=2$, then the edge
$\varphi(v)\varphi(u)$ is one of the two $(\xi,\xi+j)\sim(\xi\pm 1,\xi+j\mp
1)$.

###### Proof.

A simple application of the triangle inequality. ∎

######  Lemma 2.4.

Suppose $R_{j},R_{j-2}\neq\emptyset$ whereas $R_{j-1}=\emptyset$, then there
exists an edge between $R_{j}$ and $R_{j-2}$.

###### Proof.

Since $A_{1}$ is connected, there must be a path between $R_{j}$ and
$R_{j-2}$. Consider a shortest such path. It must completely reside in
$R_{j}\cup R_{j-1}\cup R_{j-2}$, and since $R_{j-1}=\emptyset$, its first step
outside of $R_{j}$, must be to a vertex in $R_{j-2}$, as claimed. ∎

The previous two lemmas clearly apply to $L$ as well.

######  Lemma 2.5.

If $\left|j\right|<\ell$, then either $R_{j}$ or $L_{-j}$ must be empty.

###### Proof.

We show that if there exist vertices $v\in R_{j}$, $u\in L_{-j}$, then $G$ is
not geodetic, because $d(u,v)$ is realized by two distinct paths. Any $u,v$
path must clearly traverse either $x$ or $y$. But the assumption that
$\left|j\right|<\ell$ implies that the shortest $u,x,v$ path cannot traverse
$y$ and the shortest $u,y,v$ path cannot traverse $x$. In particular, the
shortest $u,x,v$ path and $u,y,v$ path in $G$ are distinct. Moreover, they
have the same length, because the shortest length of a $u,y,v$ resp. $u,x,v$
paths is $d(u,y)+d(y,v)$ resp. $d(u,x)+d(x,v)$. Since
$d(u,y)-d(u,x)=j=d(v,x)-d(v,y)$, they have the same length, as claimed. ∎

It follows from 2.5 that at least one of $R_{0},L_{0}$ must be empty. We
denote below $\Pi=x,x_{1},x_{2},\ldots,x_{\ell-1},y$. In particular, if
$\ell=1$, then $x_{1}=y$. We need the following lemma.

######  Lemma 2.6.

If both $R_{\ell-1}=R_{\ell-3}=\emptyset$, then $R_{\ell}=\\{x\\}$. In
particular, $x_{1}$ is the only neighbor of $x$ in $A_{1}\cup\Pi$.

###### Proof.

The vertex $x_{1}$ has degree at least $3$, and must therefore have a neighbor
in $R$. But by assumption $R_{\ell-1}=R_{\ell-3}=\emptyset$, so $x_{1}$ must
have a neighbor in $R_{\ell-2}$. Consequently, $x_{1}$ is not the only vertex
in $R_{\ell-2}$. The graph $\varphi[A_{1}]$ is connected, and since
$\varphi^{-1}(0,\ell)=\\{x\\}$, it does not contain the vertex $(0,\ell)$, nor
the edge $(0,\ell)\sim(1,\ell-1)$. Let us assume toward contradiction that
$R_{\ell}$ is comprised not only of $x$. Then
$\varphi[R_{\ell}]\setminus\\{(0,\ell)\\}$ and $R_{\ell-2}$, are nonempty
whereas $R_{\ell-1}=\emptyset$. By 2.4, there exists an edge
$(\xi,\xi+\ell)\sim(\xi+1,\xi+\ell-1)$. Let $v_{\xi}u_{\xi}\in E(G)$ be a pre-
image of this edge. Namely,
$\varphi(v_{\xi})=(\xi,\xi+\ell),\varphi(u_{\xi})=(\xi+1,\xi+\ell-1)$. Clearly
$\pi(v_{\xi},x)$ must be contained in $R_{\ell}$. Moreover, $\pi(u_{\xi},y)$
does not go through $x$ because $d(u_{\xi},y)-d(u_{\xi},x)=\ell-2$. Therefore,
$\pi(v_{\xi},x)*\Pi$ and $v_{\xi}*\pi(u_{\xi},y)$ are two distinct $v_{\xi},y$
geodesics - contrary to the assumption of geodeticity.

∎

A similar lemma can be proved for $R_{-\ell}$: If both
$R_{1-\ell}=R_{3-\ell}=\emptyset$, then $R_{-\ell}=\\{y\\}$. In particular,
$x_{\ell-1}$ is the only neighbor of $y$ in $A_{1}\cup\Pi$.

Figure 2: Illustration of 2.6. The existence of the dotted edge follows from
the assumption that $x$ is not the only vertex of $R_{\ell}$.

We can now prove 1.1. See 1.1

###### Proof.

The argument runs as follows: The sets $R_{j}$ are nonempty for every other
value of $j$. To wit, $R_{\ell-2j}$ is nonempty for any $1\leq j\leq\ell-1$,
since $R_{\ell-2j}$ contains the vertex $x_{j}$. But then 2.5 implies that
$L_{\ell-2j}=\emptyset$, see 3(b). We claim that $L_{\ell-1}$ and $L_{1-\ell}$
are nonempty, thus repeated application of 2.4 results in $L_{k}\neq\emptyset$
for any $k\not\equiv\ell\mod 2$. Therefore, $R_{k}=\emptyset$ for such $k$.
Now we satisfy the assumptions of 2.6, so $R_{\ell}=\\{x\\}$. But then
$\\{x_{1},y\\}$ is a vertex cut. If $xy\in E(G)$, then $x_{1}=y$, contrary to
$G$ being $2$-connected. Otherwise, $d(x_{1},y)<d(x,y)$ \- contrary to the
minimality of $\ell$.

It is left to justify that $L_{\ell-1},L_{1-\ell}$ are nonempty. The neighbors
of $x$ in $A_{2}$ reside in $L_{\ell},L_{\ell-1}$. If $x$ does not have a
neighbor in $L_{\ell}$, we are done, so suppose $x$ has a neighbor in
$L_{\ell}$, and $y$ has a neighbor $v_{y}\in L_{-\ell}\cup L_{1-\ell}$. Since
$A_{2}$ is connected, there must be a path connecting these vertices. Consider
a shortest such path, and its first step outside of $L_{\ell}$. It cannot be a
vertex in $L_{\ell-2}$, so it must be in $L_{\ell-1}$. ∎

(a) Stage 1

(b) Stage 2: $R_{\ell-2j}\neq\emptyset$

(c) Stage 3: $L_{k}\neq\emptyset$ for $k\not\equiv\ell\mod 2$

(d) Stage 4: $R_{\ell}=\\{x\\}$

Figure 3: Illustration of the proof: Black lines represent diagonals which are
known to be nonempty. Dotted lines stand for the presently undecided cases. A
diagonal whose status is decided becomes black if proven nonempty, and deleted
if empty.

##  3 Geodetic blocks of diameter 4 and 5

In this section, we construct two families of geodetic blocks, the graphs in
which have diameter $4$ and $5$. We need some notation first. Let $v$ be a
vertex in a graph $G=(V,E)$ and let $i\geq 0$ be an integer. Clearly
$|d(v,x)-d(v,y)|\leq 1$ for every edge $e=xy$ in $G$. We say that $e$ is
$v$-horizontal resp. $v$-vertical if $d(v,x)=d(v,y)$ resp.
$|d(v,x)-d(v,y)|=1$. Note that every edge in every shortest $v\to u$ path is
$v$-vertical.

######  Proposition 3.1.

$G$ is geodetic if and only if for every $v\in V$ the $v$-vertical edges form
a spanning tree.

###### Proof.

It is easy to see that the $v$-vertical edges form a spanning subgraph in
every connected graph. Suppose that $G$ is not geodetic, and let us find some
vertex $w$ such that the $w$-vertical edges in $G$ do not form a spanning
tree, as there is a cycle comprised of $w$-vertical edges. Indeed, since $G$
is not geodetic, it has vertices $v,u$ with two distinct shortest paths
between them $\pi\neq\pi^{\prime}$. But all the edges in $\pi,\pi^{\prime}$
are $v$-vertical, and together they contain a cycle, as claimed.

Conversely let $v$ be a vertex in a geodetic graph $G$, and let $T$ be a BFS
tree rooted at $v$. Clearly all edges in $T$ are $v$-vertical, and as we show,
all edges $xy\notin T$ are $v$-horizontal. Indeed, if $xy$ is $v$-vertical,
with $d(v,x)=i$ and $d(v,y)=i+1$, this yields two distinct shortest paths from
$v$ to $y$. ∎

We mostly follow the notation and terminology of [13]. Let $q$ be a prime
power, and let $PG_{2}(q)$ and $AG_{2}(q)$ be a projective resp. affine plane
of order $q$. The point sets of these geometries is denoted by $P$, and their
sets of lines (blocks) by $\mathcal{L}$. Their point-line incidence relation
is denoted by $\mathcal{I}\subset P\times\mathcal{L}$. Elements of
$\mathcal{I}$ are called _Flags_. The _Levi Graph_ of an incidence structure
$\SS=(P,\mathcal{L},\mathcal{I})$, denoted $Levi(\SS)$ is the bipartite graph
with vertex sets $P\sqcup\mathcal{L}$, where $p$ and $L$ are neighbors iff $p$
is incident with $L$.

The _Flag graph_ of $\SS$ is denoted $Flag(\SS)$. Its vertex set is
$P\sqcup\mathcal{I}$. It has two kinds of edges: between a point $p$ and flag
$(p,L)$. In addition $(p,L)\sim(p^{\prime},L)$ for every two points
$p,p^{\prime}$ of the same line $L$. As we show below $Flag(\SS)$ is geodetic,
and has diameter $4$ when $\SS=PG_{2}(q)$ and $5$ if $\SS=AG_{2}(q)$. To fix
ideas, associated with each $L\in\mathcal{L}$ in $Levi(\SS)$ is a porcupine, a
clique of size $|L|$, plus an edge $p\sim(p,L)$ emanating from $(p,L)$ for
every $p\in L$. Therefore, to every simple path $Q$ in $Levi(\SS)$ there
corresponds a simple path $\hat{Q}$ in $Flag(\SS)$. Namely, if $Q$ traverses
through $L$, that is $[p,L,p^{\prime}]$, the corresponding steps in $\hat{Q}$
$[p,(p,L),(p^{\prime},L),p^{\prime}]$, which is a simple path in $Flag(\SS)$.
Recall that a graph is $2$-connected if and only if every two of its vertices
lie on a simple cycle. We conclude:

######  Corollary 1.

If $Levi(\SS)$ is $2$-connected, then so is $Flag(\SS)$.

###  3.1 Properties of $Flag(AG_{2}(q))$

Recall the following properties of $AG_{2}(q)$:

  1. 1.

It has $q^{2}$ points and $q^{2}+q$ lines.

  2. 2.

Every point is incident with $q+1$ lines

  3. 3.

Every line has $q$ points

  4. 4.

If a point $p$ is not in a line $L$, then there exists a unique line
$L^{\prime}$ with $p\in L^{\prime}$ such that $L$ and $L^{\prime}$ are
disjoint. The common practice is to say that $L$ and $L^{\prime}$ are parallel
and denote $L\parallel L^{\prime}$.

We denote $\mathscr{F}(q)=Flag(AG_{2}(q))$. Properties 1 and 3 imply that the
number of vertices in $\mathscr{F}(q))$ is $q^{3}+2q^{2}$. We denote by
$L_{\alpha,\beta}$ the unique line that contains the two points
$\alpha,\beta$.

######  Proposition 3.2.

$\mathscr{F}(q)$ is 2-connected.

###### Proof.

We exhibit a simple cycle through any two vertices in $AG_{2}(q)$. Consider
all cycles of the form

$(L_{1},x_{1},L_{x_{1},x_{2}},x_{2},L_{2},x,L_{1})$

where $L_{1},L_{2}$ are two distinct intersecting lines with $L_{1}\cap
L_{2}=x$, and $x_{1},x_{2}$ are points in $L_{1},L_{2}$ respectively, other
than $x$. These yield cycles through any two vertices in $\mathscr{F}(q)$
other than a pair of parallel lines. Finally, here is a simple cycle through
two parallel lines $L_{1},L_{2}$

$(L_{1},x_{1},L_{x_{1},x_{2}},x_{2},L_{2},x^{\prime}_{2},L_{x_{1}^{\prime},x_{2}^{\prime}},x_{1}^{\prime},L_{1}).$

Here $x_{1},x_{1}^{\prime},x_{2},x_{2}^{\prime}$ are distinct points on
$L_{1},L_{2}$. This completes the proof. ∎

######  Theorem 3.3.

$\mathscr{F}(q)$ is geodetic and of diameter $5$.

###### Proof.

We show that the collection of $v$-vertical edges form a tree for every vertex
$v$ in $\mathscr{F}(q)$. There are just two cases to consider: $v=\mathbf{p}$,
a point in $P$ or a flag $v=\mathbf{(p,L)}\in\mathcal{I}$. Let
$\mathcal{V}(i)$ be the number of $v$-vertical edges $\alpha\beta\in E$ of
height $i$, i.e., $\\{(d(v,\alpha),d(v,\beta)\\}=\\{i-1,i\\}$. Let $N_{i}(v)$
be the $i$-sphere centered at $v$, that is $N_{i}(v)=\left\\{u\in V\mid
d(v,u)=i\right\\}$. We analyze $N_{i}(v)$ in either case.

####  $\mathbf{v=p}$:

  1. 1.

Clearly $N_{1}(\mathbf{p})=\left\\{(\mathbf{p},L)\in\mathcal{I}\right\\}$, so
$\mathcal{V}(1)=|N_{1}(\mathbf{p})|=q+1$.

  2. 2.

Each $(\mathbf{p},L)\in N_{1}(\mathbf{p})$ is adjacent to all the vertices in
the clique defined by $L$. This contributes $q-1$ vertical edges. Also,
$N_{2}(\mathbf{p})=\left\\{(x,L)\mid\mathbf{p}\in L,x\neq p\right\\}$, since
these cliques are disjoint. It also follows that
$\mathcal{V}(2)=|N_{1}(p)|\cdot(q-1)=(q^{2}-1)$.

  3. 3.

Let $(x,L)\in N_{2}(\mathbf{p})$. The neighbors of $(x,L)$ are $x$ and $(y,L)$
for $y\neq x$ in $L$. All the latter are in $N_{2}(\mathbf{p})$, so every
$(x,L)\in N_{2}(\mathbf{p})$ contributes exactly one vertex to
$N_{3}(\mathbf{p})$. Consequently, $N_{3}(v)=\left\\{x\mid
x\neq\mathbf{p}\right\\}$, and $\mathcal{V}(3)=\mathcal{V}(2)=(q^{2}-1)$.

  4. 4.

Each $x\neq\mathbf{p}$ is incident with $q+1$ lines, only one of which is
$L_{\mathbf{p},x}$. Therefore, $x$ is adjacent to $q$ flags $(x,L^{\prime})$,
one for each $L^{\prime}\neq L_{\mathbf{p},x}$. These flags are clearly
distinct, therefore $N_{4}(v)=\left\\{(x,L^{\prime})\mid L^{\prime}\neq
L_{\mathbf{p},x}\right\\}$ and
$\mathcal{V}(4)=q\cdot\mathcal{V}(3)=q(q^{2}-1)$.

The calculation checks:

$\overbrace{(q+1)}^{\mathcal{V}(1)}+\overbrace{(q^{2}-1)}^{\mathcal{V}(2)}+\overbrace{(q^{2}-1)}^{\mathcal{V}(3)}+\overbrace{q(q^{2}-1)}^{\mathcal{V}(4)}=q^{3}+2q^{2}-1=|V(\mathscr{F}(q))|-1.$

Figure 4: $\mathscr{F}(3)$, as seen from $v=\mathbf{p}$. The colors have no
mathematical significance and are only intended for better visibility.

####  $\mathbf{v=(p,L)}$:

This case is a bit trickier. Let $x\neq\mathbf{p}$ be a point on $\mathbf{L}$.
Let $y$ be a point not on $\mathbf{L}$, and $\ell_{y}$ the unique line through
$y$ that is parallel to $\mathbf{L}$. Finally, we denote by
$\left\\{\mathbf{L}^{i}_{x}\right\\}_{i=0}^{q}$ the lines through $x$, where
$\mathbf{L}=\mathbf{L}_{x}^{0}$.

  1. 1.

$N_{1}(v)=\\{\mathbf{p}\\}\sqcup\\{(x,\mathbf{L})\mid x\neq\mathbf{p}\\}$, so
$\mathcal{V}(1)=1+(q-1)=q$. We refer below to descendants of $\mathbf{p}$ as
the left vertices, and to descendants of $\\{(x,\mathbf{L})\mid
x\neq\mathbf{p}\\}$ as right vertices (see Figure 5).

  2. 2.

The neighbors of $\mathbf{p}$ other than $\mathbf{(p,L)}$ are
$\left\\{(\mathbf{p},\mathbf{L}_{\mathbf{p}}^{i})\right\\}_{i\neq 0}$, so the
left side in $N_{1}(v)$ contributes $q$ edges of height $2$. The right
vertices in $N_{1}(v)$ form a clique, with a porcupine structure. Therefore,
each vertex of this clique contributes a single height $2$ edge, namely
$(x,\mathbf{L})\sim x$. So
$N_{2}(\mathbf{(p,L)})=\left\\{(\mathbf{p},\mathbf{L}^{i}_{\mathbf{p}})\right\\}_{i\neq
0}\sqcup\left\\{x\mid\mathbf{p}\neq x\in\mathbf{L}\right\\}$ and
$\mathcal{V}(2)=q+(q-1)$.

  3. 3.

Each left vertex in $N_{2}(v)$ is adjacent to a clique
$\left\\{(y,\mathbf{L}^{i}_{\mathbf{p}})\right\\}_{y\neq\mathbf{p}}$ of $q-1$
flags, so each $(\mathbf{p},\mathbf{L}^{i}_{\mathbf{p}})$ contributes $(q-1)$
distinct edges of height $3$. As for the right side, the edges
$x\sim(x,\mathbf{L}^{i}_{x})$ have height $3$, and each $x\neq\mathbf{p}$
contributes $q$ of them.
So, $N_{3}(v)=\left\\{(y,\mathbf{L}^{i}_{\mathbf{p}})\mid y\neq p,i\neq
0\right\\}\sqcup\left\\{(x,\mathbf{L}_{x}^{i})\mid x\neq\mathbf{p},i\neq
0\right\\}$ and $\mathcal{V}(3)=q(q-1)+q(q-1)$.

  4. 4.

For every $y\notin\mathbf{L}$, there holds
$L_{\mathbf{p},y}=\mathbf{L}_{\mathbf{p}}^{i}$ for some $i\neq 0$. Therefore,
the left side vertices of $N_{3}(v)$ are partitioned into cliques in
$N_{3}(v)$, and cover all $y\notin\mathbf{L}$. Hence each vertex contributes a
unique edge $(y,L_{\mathbf{p},y})\sim y$ of height $4$. As for the right side:
Every edge $(x,\mathbf{L}_{x}^{i})$ of height $4$ is adjacent to the clique
$\left\\{(y,L_{x}^{i})\mid y\neq x\right\\}$. There are exactly $q-1$ such
vertices for each $(x,\mathbf{L}_{x}^{i})$. So $N_{4}(v)=\left\\{y\mid
y\notin\mathbf{L}\right\\}\sqcup\left\\{(y,\mathbf{L}_{x}^{i})\mid
x\in\mathbf{L},y\notin\mathbf{L},i\in[q]\right\\}$ and
$\mathcal{V}(4)=q(q-1)+q(q-1)^{2}$.

  5. 5.

The edges $(y,L_{x}^{i})\sim y$ are horizontal (between the two sides of
$N_{4}(v)$), so the only $5$-vertical edges are of the form
$y\sim(y,\ell_{y})$ \- and since $\ell_{y}$ is unique, $\mathcal{V}(5)=q(q-1)$
and $N_{5}(v)=\left\\{(y,\ell_{y})\mid y\notin\mathbf{L}\right\\}$.

Once again, the calculation checks:

$\overbrace{1+(q-1)}^{\mathcal{V}(1)}+\overbrace{q+(q-1)}^{\mathcal{V}(2)}+\overbrace{q(q-1)+q(q-1)}^{\mathcal{V}(3)}+\overbrace{q(q-1)+q(q-1)^{2}}^{\mathcal{V}(4)}+\overbrace{q(q-1)}^{\mathcal{V}(5)}=q^{3}+2q^{2}-1.$

This analysis also establishes that $\mathscr{F}(q)$ has diameter 5. such
edges. Each $x\in L$ lies on $q$ lines other than $L$, so each $x$ contributes
$p$ additional $3$-vertical edges of the form $x(x,L^{\prime})$ for a total of
$q(q-1)$ such edges. Each such $L^{\prime}$ contains $p-1$ points other than
$x$, and said points d not lie on $L$. Thus each $(x,L^{\prime})$ contributes
$p-1$ vertical edges of the form $(x,L^{\prime})(y,L^{\prime})$, for a total
of $q\cdot(q-1)^{2}$ edges. Neighbors of $(y,L^{\prime})$ are the points $y$,
which we are of distance $4$ from $(p,L)$ \- as we see in the fllowing part. ∎

Figure 5: $\mathscr{F}(3)$, as seen from $v=\mathbf{(p,L)}$.

###  3.2 Properties of $Flag(PG_{2}(q))$

Recall the following properties of $PG_{2}(q)$:

  1. 1.

It has $q^{2}+q+1$ points and the same number of lines.

  2. 2.

Every point is incident with $q+1$ lines, and every line has $q+1$ points.

These properties imply that $\left|V(Flag(PG_{2}(q))\right|=(q+1)^{3}+1$.

######  Theorem 3.4.

$Flag(PG_{2}(q))$ is $2$-connected, geodetic and has diameter $4$.

###### Proof.

By Corollary 1, if $Levi(PG_{2}(q))$ is $2$-connected, then so is
$Flag(PG_{2}(q))$. To show that $Levi(PG_{2}(q))$ is $2$-connected, it
suffices to use the first cycle that is described in the proof of 3.2. The
proof of geodeticity is a slight adaptation of the proof of Theorem 3.3. The
numbers change somewhat, and what’s more, since no lines are parallel, we do
not reach $N_{5}(v)$ in the second case. Consequently, the diameter is $4$. ∎

##  4 Discussion

Geodetic blocks with $\delta(G)\geq 3$ (which, by Theorem 1.1, are $3$
connected) seem hard to find. Specifically, we ask:

  1. 1.

We recall our question whether geodetic blocks of $\delta(G)\geq 3$ can have
arbitrarily large diameter. Also, can they have arbitrarily large girth? The
two questions are closely related since the diameter of a graph is at least
half its girth.

  2. 2.

So far, we only know of three cubic geodetic blocks - the Petersen Graph,
$K_{4}$ and $Flag(PG_{2}(2))$. Is this list exhaustive? Is the number of such
graphs finite?

  3. 3.

Is the study of geodetic graphs related to structural graph theory, and more
concretely to the family of _even-hole-free graphs_ [14]? The origin of this
question is this: If $u,v$ are two antipodal vertices in an induced even cycle
(aka an even hole) $C$ in a geodetic graph, then the $uv$ geodetic is not
included in $C$.

## References

  * [1] A Blokhuis and AE Brouwer, _Geodetic graphs of diameter two_ , Geometries and Groups, Springer, 1988, pp. 527–533.
  * [2] Michael Franklyn Bridgland, _Geodetic graphs and convexity_ , Ph.D. thesis, Louisiana State University and Agricultural & Mechanical College, 1983.
  * [3] Murray Elder and Adam Piggott, _Rewriting systems, plain groups, and geodetic graphs_ , Theoretical Computer Science 903 (2022), 134–144.
  * [4] Dmitriy Gorovoy and David Zmiaikou, _On graphs with unique geodesics and antipodes_ , arXiv preprint arXiv:2111.09987 (2021).
  * [5] Ladislav Nebeskỳ, _New proof of a characterization of geodetic graphs_ , Czechoslovak Mathematical Journal 52 (2002), no. 1, 33–39.
  * [6] Oystein Ore, _Theory of graphs_ , American Mathematical Society, 1962.
  * [7] KR Parthasarathy and N Srinivasan, _Geodetic blocks of diameter three_ , Combinatorica 4 (1984), no. 2, 197–206.
  * [8] Raffaele Scapellato, _Geodetic graphs of diameter two and some related structures_ , Journal of Combinatorial Theory, Series B 41 (1986), no. 2, 218–229.
  * [9] N Srinivasan, J Opatrny, and VS Alagar, _Construction of geodetic and bigeodetic blocks of connectivity k-greater-than-or-equal-to-3 and their relation to block-designs_ , Ars Combinatoria 24 (1987), 101–114.
  * [10] Joel G Stemple, _Geodetic graphs of diameter two_ , Journal of Combinatorial Theory, Series B 17 (1974), no. 3, 266–280.
  * [11] Joel G Stemple, _Geodetic graphs homeomorphic to a complete graph_ , Annals of the New York Academy of Sciences 319 (1979), no. 1, 512–517.
  * [12] Joel G Stemple and Mark E Watkins, _On planar geodetic graphs_ , Journal of Combinatorial Theory 4 (1968), no. 2, 101–117.
  * [13] Jacobus Hendricus van Lint and Richard Michael Wilson, _A course in combinatorics_ , Cambridge university press, 2001.
  * [14] Kristina Vušković, _Even-hole-free graphs: a survey_ , Applicable Analysis and Discrete Mathematics (2010), 219–240.
  * [15] Bohdan Zelinka, _Geodetic graphs of diameter two_ , Czechoslovak Mathematical Journal 25 (1975), no. 1, 148–153.