Can expressing there is an edge that connects two vertexes be expressed using only first-order logic? Suppose that we want to express "there exists
two vertexes that can be shown to be connected
by an edge." in first-order logic. Can this
statement be expressed using only first-order
logic? Or does this require something more? I am
confused because "connected by an edge" seems
to be somehow awkward to express in first-order
logic (if this is not true, are we expressing edge
connectivity using there exists a set E that...?).
 A: Define the domain/universe to be the set of all edges and vertices.
Now, first-order logic permits/included the use of predicates and quantifiers.
So we can define predicates as such: 


*

*$V(x): $ "x is a vertex"

*$E(x): $ "x is an edge"

*$C(x, y, z): $ "x and y are connected by z" (or "it can be shown that x and y are connected by z")

*$x = y:$ "x is identical to y" (If you prefer, we can use $I(x, y)$ to denote that "x is identical to y")


Since we are speaking of the existence of two vertices, and the existence of an edge that connects $x$ and $y$, we use the existential quantifier, $\,\exists,\,$ for each variable $x, y, z$:
Then to say "there are two vertices which are connected by some edge" (or "there exist two vertices and they can be shown to be connected by some edge", respectively), we write:

$$\exists x \exists y \exists z\big(V(x) \land V(y) \land \lnot(x = y) \land C(x, y, z)\big)$$

which is equivalent to:

$$\exists x \exists y \big(V(x) \land V(y) \land \lnot(x = y) \land \exists z(C(x, y, z))\big)$$




*

*Feel free to replace $\,\lnot (x = y)\,$ with $\,\lnot I(x, y)\,$, as it is defined above. 

*Note that we need to add the clause $\,\lnot(x = y)\,$ to make explicit
that we are ruling out that $x, y$ refer to the same vertex.

