2
$\begingroup$

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.

3 Answers 3

2

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.

  • 0
    thanks for the reply. For #1 i got this so far, ∀n number of vertices ∃k such that G(k,n) holds. Am i missing anything?2012-01-24
  • 0
    Almost, but I think you're mixing up the order of your conditionals there. If I'm interpreting it right, your statement says "For every set of n vertices, there's a vertex connected to all of them". This would work if the graph had n vertices, but unfortunately the size of the graph isn't given. Try doing something more like the statement I wrote - something like "There exists a vertex V, such that for every other vertex W, V is connected to W." When dealing with atomic statements like these, rewriting them in plain English is a really good sanity check.2012-01-24
  • 1
    Got it. ∃v such that ∀w G(v,w) holds.2012-01-24
  • 1
    for #2; ∀v ∀w such that G(v,w) holds.2012-01-24
  • 1
    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.2012-01-24
  • 1
    for #3; ∀v ∀w ∃a ∃b such that G(v,a) and G(a,b) and G(b,w) hold.2012-01-24
  • 0
    How about #4; ∀v ∀w ∃a such that G(v,a) and G(a,w) and G(w,v) does not hold.2012-01-24
  • 0
    @janeii, that is incorrect, but close. What that says is that every pair of vertices does not form a triangle with _all_ other vertices.2012-01-24
  • 0
    @DanBrumleve corrected; ∃v ∃w ∃a such that G(v,a) and G(a,w) and G(w,v) does not hold.2012-01-24
  • 0
    Still nope! That says there exist three nodes which do not form a triangle, but we are looking for the statement that _no_ three nodes form a triangle. [De Morgan's law](http://en.wikipedia.org/wiki/De_Morgan's_laws) may help here but it will also take some practice and deep thinking to internalize the formalization.2012-01-24
  • 0
    @DanBrumleve, ∀v ∀w ∀a such that not G(v,a) or not G(a,w) or not G(w,v)2012-01-24
  • 0
    You got it! (but you don't need to say "such that" except after "there exists"...)2012-01-24
  • 0
    @DanBrumleve and the last one, ∃v ∃w ∃a ∃b such that G(v,w) or G(w,v) or G(v,a) ... and so on ... >= 1.2012-01-24
  • 0
    @janeiii, 5. should start with "for _all_ four vertices"...2012-01-24
  • 1
    Corrected; ∀v ∀w ∀a ∀b G(v,w) or G(w,v) or G(v,a) ... and so on ... >= 1.2012-01-24
  • 1
    @janeiii: As a matter of style, you shouldn't be using symbols such as $\forall$ and $\exists$ together with English words like "such as" and "and". Once you've started a formula symbolically, stick to symbols until the formula is finished, that is with $\wedge$ for "and" and so forth. The meaning of the $\forall$ and $\exists$ symbols _includes_ "such that" in each case; writing it out explicitly is redundant.2012-01-24
1

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.

  • 0
    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.2012-01-24
  • 0
    @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?2012-01-24
  • 1
    @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?2012-01-24
  • 0
    @André, insightful as always! And my answer is wrong. :(2012-01-24
  • 0
    @Dan Brumleve: It may be the intended one!2012-01-24
-1
  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.

  • 0
    The OP asks how to approach the problem, so just providing straight-up answers probably won't help them much to learn.2012-01-24
  • 0
    @Lopsy, edited to explain my approach.2012-01-24
  • 0
    @DanBrumleve thanks.2012-01-24