0

Let $G$ be a graph, which must have at least one node, i.e. the set of nodes and edges cannot be empty. Let $R$ be a symmetric and irreflexive relation for $G$ and each vertex. I would like to build a formula, such that if a graph $G$ with $n \geq 3$ nodes is a model of that formula, there exists no $n$-cycle, meaning that there is no cycle between all existing nodes $n$.

My idea was, to first express that $R$ is irreflexive and symmetric, so

$\forall a \forall b ((Rab \leftrightarrow Rba) \land \lnot Raa \land Rbb)$

and then include that there must exist one node $c$, which has only one edge. Because then, we can be certain there exists no cycle. I am not sure though if I need to include all nodes to formulate this, or if something like $\exists c \forall d$ is enough?

Any hints are appreciated!

kklaw
  • 301
  • 1
  • 9
  • 1
    Hint: How would you say it in a human language? Let's say $n=3$: "there are no three elements $a_1,a_2,a_3$ such that $Ra_1a_2, Ra_2a_3, Ra_3a_1$. Now formalise (translate to predicate logic). Now generalise to $n>3$. –  Jan 04 '22 at 11:14
  • 1
    Also the presence of a node with one edge is a red herring. Presence or absence of such node has no bearing on whether the graph will have a cycle. –  Jan 04 '22 at 11:15
  • But if we are talking about a $n$-cylce of a graph having $n$ nodes, meaning all nodes must be included in the cycle, then every node must have $2$ edges, no? Regarding your first comment I would suggest something like $ \lnot \exists a_1 \lnot \exists a_2 .... \lnot \exists a_n ( \bigwedge Ra_i a_j)$ – kklaw Jan 04 '22 at 11:17
  • Ah, that is what you mean. I misread your question - I thought it was about "a graph without cycle of size $n\ge 3$" rather than "a graph with $n$ nodes and without cycle of size $n$, where $n\ge 3$. (Note your graph may still have smaller cycles.) –  Jan 04 '22 at 11:21
  • 1
    Beware: $\lnot(\exists x)\lnot(\exists y)(\ldots)$ is not the same as $\lnot\left((\exists x)(\exists y)\ldots\right)$. The first one, for example, means $(\forall x)(\exists y)(\ldots)$... But you would be on the right track. –  Jan 04 '22 at 11:24
  • Yeah, I wanted to change it to only one $\lnot$, but couldn't because of the the limit. My sort of final answer would be $\lnot \exists a_1 \exists a_2 ... \exists a_n ( \bigwedge_{i \neq j < n} R a_i a_j )$ and then I probably have to add the irreflexive and symmetry condition for all $a_1 ... a_n$? – kklaw Jan 04 '22 at 11:26
  • 1
    You just want $\bigwedge_{i=1}^{n-1}Ra_iRa_{i+1}\wedge Ra_na_1$ –  Jan 04 '22 at 12:23
  • As for irreflexive and symmetric, again don't let me misinterpret your question: if it asks for that add them, if not - don't. (The difference is between "write axioms of a graph with $n$ vertices and no cycles of length $n$" vs. "write a formula which, among all graphs with $n$ vertices, is true precisely on those with no cycles of length $n$"...) –  Jan 04 '22 at 12:28
  • If you need to express that the graph has precisely $n$ vertices, you can do it too. –  Jan 04 '22 at 12:28
  • For clarification, your formulas basically says that if there exists $n-1$ edges $R a_i a_{i+1}$, then there is no $a$, which has a edge to one of them? Or more precisely, it cannot be the case that we have $n-1$ edges $R a_i a_{i+1}$ and one relation $R a_n a_1$ – kklaw Jan 04 '22 at 12:33
  • 1
    Yes, at least that is the intention. –  Jan 04 '22 at 12:36
  • If I would like to express irreflexivity and symmetry, would $\forall a_0 \forall a_1$ be enough or do I need to include all $a_n$? Also, thank you very much for your time and help! – kklaw Jan 04 '22 at 12:48
  • It would be enough to use one variable for irreflexivity and two for symmetry, –  Jan 04 '22 at 12:51

0 Answers0