# Expressing a relationship in a graph using quantified logic

Express the following using quantified formulae for a simple undirected graph $G = (V,E)$. The predicate P({u,v}) is true when $\{u,e\}\in E$ and false otherwise.

The diameter of $G$ is at most 2.

Can someone help me express this statement using quantified formulae? The general process seems unintuitive at this point, and I was hoping someone could clear up the confusing by making the notation easy to understand (as it relates to graphs).

-

The first step is translate diameter at most $2$ into more basic terms involving vertices and edges directly. To say that the diameter of $G$ is at most $2$ is to say that if $u$ and $v$ are any vertices of $G$, the distance between $u$ and $v$ is at most $2$. Using $d(u,v)$ for the distance between $u$ and $v$, we can translate that directly into
$$\forall u,v\in V(d(u,v)\le 2)\;.$$
Now we have to expand the notion of distance between two vertices, translating it into simpler concepts. We don’t actually need the whole concept, though: we just need to know exactly what it means for the distance to be at most $2$. The distance between $u$ and $v$ is $0$ if $u=v$, $1$ if $\{u,v\}\in E$ (assuming that loops are not allowed), and $\le 2$ if there is a vertex $w\in V$ such that $\{u,w\},\{w,v\}\in E$. Taking it in easy steps:
\begin{align*} &\forall u,v\in V(d(u,v)\le 2)\\\\ &\qquad\text{iff}\quad\forall u,v\in V\Big(u=v\lor \{u,v\}\in E\lor\exists w\in V(\{u,w\}\in E\land\{w,v\}\in E)\Big)\\\\ &\qquad\text{iff}\quad\forall u,v\in V\Big(u=v\lor P(u,v)\lor\exists w\in V(P(u,w)\land P(w,v)\Big)\;. \end{align*}