Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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*}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.