# Express the following statements using quantifiers and atomic statements

How do i approach this problem?

Let G represent a graph with vertices V. The only atomic statements about the graph are of the form G(v,w) where v and w are vertices in V and G(v,w) means there is an edge between v and w. The quantifiers ∀x and ∃x refer to the vertex set V. With this context, express the following statements about the graph G formally using quantifiers and atomic statements:

1. There is some vertex in the graph that has an edge connecting it to every other vertex.
2. The graph is the complete graph.
3. Any two vertices are connected by a path of length 3.
4. The graph contains no triangle.
5. Among any four vertices at least two are connected by an edge.
-
–  lhf Jan 24 '12 at 3:36

I'll reword each of your three constraints in a way that's closer to the atomic-statement formulation:

1. There exists a vertex in the graph, such that for every other vertex, there is an edge between the two.

2. Any two vertices have an edge between them.

3. For any two vertices that we want to connect, we can find two new vertices to form a path between them (i.e. the first original vertex is connected to the first new vertex, the two new vertices are connected, etc.)

Comment if you need more guidance.

-
Got it. ∃v such that ∀w G(v,w) holds. –  janeiii Jan 24 '12 at 4:29
for #2; ∀v ∀w such that G(v,w) holds. –  janeiii Jan 24 '12 at 4:31
Great! Both of those look completely right to me. #3, 4, and 5 are harder, but given your answers to the first two parts, I think you can do them without too much trouble. –  Lopsy Jan 24 '12 at 4:35
for #3; ∀v ∀w ∃a ∃b such that G(v,a) and G(a,b) and G(b,w) hold. –  janeiii Jan 24 '12 at 4:40
Corrected; ∀v ∀w ∀a ∀b G(v,w) or G(w,v) or G(v,a) ... and so on ... >= 1. –  janeiii Jan 24 '12 at 5:55

Here is a start, sort of. The problem is that I cannot think of a way of doing it in my preferred way without using the equality symbol $\:=$. (So I am working in the predicate calculus with equality.)

$1$. We want to say roughly that there is an $x$ such that for all $y$, $x$ and $y$ are joined by an edge. But more precisely, we probably don't quite want to say this, for we probably do not want to say that the $x$ is joined to itself. That complicates things slightly. Ask yourself whether the following does the job: $$\exists x\forall y(\lnot(x=y)\implies G(x,y)).$$

Equivalently, we can use $\exists x\forall y((x=y)\lor G(x,y))$

But this allows for the possibility that the point $x$ is connected by an edge to itself. If we want to rule that out explicitly, we can use $\exists x(\lnot G(x,x)\land \forall y(\lnot(x=y)\implies G(x,y)))$

$2$. The idea is quite similar to the one in Problem $1$, except that we have to say that for all $x$ and $y$, if $x\ne y$ then $x$ and $y$ are joined by an edge. Here I am interpreting "any two vertices" as meaning any two distinct vertices.

$3$. We need to interpret the meaning of the informal sentence. Is it any two vertices or is it any two distinct vertices? And do we allow the possibility of loops? I will assume no loop is being used, and that the two vertices we want to say are linkable are distinct. So we want to say that for any $x$ and $y$, if $x\ne y$, there exist objects (vertices) $u$ and $v$ such that $x\ne u$, and $x$ and $u$ are joined by an edge, and $u\ne v$, and $u$ and $v$ are joined by an edge, and $v\ne y$, and $v$ and $y$ are joined by an edge. The sentence will be kind of long, but not terribly complicated in structure.

$4.$ We want to say that for all vertices $x$, $y$, and $z$, these vertices do not form a triangle. You will have to decide whether your sentence allows loops, that is, whether $G(x,x)$ is allowed.

$5$. We want to say that for any $w$, $x$, $y$, $z$, presumably distinct, $w$ and $x$ are joined by an edge, or $w$ and $y$ are, or $w$ and $z$ are or $\dots$.

Comment: If we want to interpret $1$ as saying that there is a vertex connected to everybody, including itself, things are much easier. We can simply write $\exists x\forall y G(x,y)$. But that is probably not what a graph-theorist intends.

-
Nicolas Thank you –  janeiii Jan 24 '12 at 4:49
You are welcome. If we really cannot use $=$, you should be able to use what I wrote, getting rid of all the $\lnot(u=v)$ kind of stuff. The downside is that the sentences will not have their ordinary graph-theoretic meaning, since loops (edge connected to itself) is not being ruled ou. –  André Nicolas Jan 24 '12 at 6:18
@André, why not just use the language of FOL-=+G and assume ∀x:¬G(x,x) as an axiom of the theory? Then ¬(x=y) isn't needed in any of the sentences, right? I think that assumption would simplify your answer? –  Dan Brumleve Jan 24 '12 at 8:59
@Dan Brumleve: Suppose we have that axiom in the background. (a) How can we say (to pick one of the questions at random) that the graph is complete? Certainly can't say $\forall x\forall y G(x,y)$, it contradicts our axiom! (b) How can we say that if we have $4$ distinct vertices, at least a pair is connected by an edge? If we try to do it in the style mentioned in comments, we need to prevent the four variables from being equal in pairs, giving the unwanted implication that any two vertices are connected by an edge? –  André Nicolas Jan 24 '12 at 12:38
@André, insightful as always! And my answer is wrong. :( –  Dan Brumleve Jan 24 '12 at 12:42
1. ∃x:∀y:G(x,y)
2. ∀x:∀y:G(x,y)
3. ∀x:∀y:∃w:∃z:G(x,w)∧G(w,z)∧G(z,y)

The way I approach these types of problems is by translating them into constrained English ("for all x, ..." "there exists a y, ...") and then rendering them with equivalent formal notation. For example, 1. can be translated as "there exists a vertex x such that for all vertices y, x and y are connected by an edge", and 2. can be translated as "for all vertices x and y, x and y are connected by an edge". When I can't figure out how to translate them as such, that is a strong hint that either the problem is ill-specified or else my own understanding of the definitions is lacking.

-
The OP asks how to approach the problem, so just providing straight-up answers probably won't help them much to learn. –  Lopsy Jan 24 '12 at 4:16
@Lopsy, edited to explain my approach. –  Dan Brumleve Jan 24 '12 at 4:38
@DanBrumleve thanks. –  janeiii Jan 24 '12 at 4:45