Express the following statements using quantifiers and atomic statements

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.