Triangle-Free Modal Graph Theory

Tabitha Williams

Sam Houston State University

Advisor: Timothy Trujillo • Collaborator: Miguel Estrada
JMM 2026 — Washington, DC

Graph Theory Foundations

What is a Graph? A graph is a set of vertices with an edge relation (\(\sim\)) that is:
  • Irreflexive: No vertex connects to itself.
    \(\forall x \neg(x \sim x)\)
  • Symmetric: Bidirectional connections.
    \(\forall x \forall y (x \sim y \rightarrow y \sim x)\)

The Language of First-Order Graph Theory

What we CAN say (Local) We use variables (\(x, y, z\)) and adjacency (\(\sim\)).

"There exists a triangle."
\(\exists x \exists y \exists z (x \sim y \land y \sim z \land z \sim x)\)
What we CAN'T say (Global) First-order logic cannot express global structural properties.

  • "The graph is connected."
  • "The graph is finite."

Modal Logic in Graph Theory

We enhance graph theory by adding operators defined by graph extensions.

\(\Diamond\varphi\)
Possibility

True if we can extend \(G\) to \(H\) where \(\varphi\) is true.

\(\Box\varphi\)
Necessity

True if \(\varphi\) holds in every possible extension of \(G\).

Hamkins & Wołoszyn, Modal Model Theory (2022)

Our Focus: The World of Triangle-Free Graphs

Definition A graph \(G\) is triangle-free if it has no triangular subgraph:
\(\forall x \forall y \forall z (x \sim z \land y \sim z \rightarrow \neg(x \sim y))\)
The Main Rule When we talk about possibility/necessity, all graph extensions must also be triangle-free.

Why Expressing Connectivity is a Big Deal

A Classic Limitation It is impossible to write a first-order formula in the language of graph theory that is true if and only if two vertices are connected by a path.
The Power of Modal Logic Modal logic quantifies over extensions, enabling a definition of connectedness.

The Modal Formula for Connectivity

Hamkins & Wołoszyn, Modal Model Theory (2022)
\[ \Box\forall c\Big[ \big( c \sim x \land \forall u,v(c \sim u \land u \sim v \land v \neq c \rightarrow c \sim v) \big) \rightarrow c \sim y \Big] \]
What this defines Think of the formula above as a predicate \(\mathrm{Conn}(x,y)\) stating that \(x\) and \(y\) are connected by a path.

A modal definition of graph connectedness is then:
\(\forall x\,\forall y\,\mathrm{Conn}(x,y)\).

Understanding the Formula

Breaking down the logic into intuition:

\[ \Box\forall c\Big[ \big( c \sim x \land \forall u,v(c \sim u \land u \sim v \land v \neq c \rightarrow c \sim v) \big) \rightarrow c \sim y \Big] \]
In Plain English The formula says that in any valid extension:
  • If a new node \(c\) is added to the graph and ...
  • if \(c\) connects to our start node \(x\)...
  • ...and \(c\) is forced to "absorb" neighbors (it connects to the neighbors of its neighbors)...
  • ...then \(c\) must eventually connect to \(y\).

Step-by-Step

Step 1: add \(c\) with \(c \sim x\).
Step 2: closure forces \(c\) to connect to every node reachable from \(x\).

Connected: closure reaches all nodes (including \(y\)) x • • y c closure adds links reaches \(y\)
Not Connected: closure reaches all it can (but not \(y\)) x • • y c closure adds links cannot reach \(y\)

This includes \(y\) exactly when \(x\) and \(y\) lie in the same component.

The Problem: Direct Connections

u v Existing edge c TRIANGLE
The Issue The original formula uses direct connections like \(c \sim x\). In triangle-free extensions, this can force a forbidden triangle immediately, breaking the logic.

The Solution: A Triangle-Free Proxy

Definition: Private-Witness \(\bowtie\) We define \(x \bowtie y\) using a witness \(z\) that connects to only \(x\) and \(y\):
\[ x \bowtie y \iff \exists z\Big( x \sim z \land y \sim z \land \forall w\,(z \sim w \rightarrow (w=x \lor w=y)) \Big). \]
x y z safe two-step link

The Adapted Formula (Triangle-Free)

Replace direct adjacency with safe \(\bowtie\) connections.

\[ \Box\forall c\Big[ \big( c \bowtie x \land \forall u,v(c \bowtie u \land u \sim v \land v \neq c \rightarrow c \bowtie v) \big) \rightarrow c \bowtie y \Big] \]
Concept Same logical shape as the general case, but every time we would force a direct edge to \(c\), we instead force a private two-step \(\bowtie\) link.

Meta-Theorem: A Bridge Between Worlds

The Goal Translate any modal formula \(\varphi\) from the general world to the triangle-free world.
The Method Build \(\varphi^*\) by replacing extension-adjacency requirements with safe \(\bowtie\)-requirements.
Truth Preservation The translated statements capture the same modal content, now restricted to triangle-free extensions.

Other Expressible Properties

Using the translation idea:

2-Colorability Easy, since 2-colorable graphs are always triangle-free.
Finiteness Expressible via special "witness" configurations built using \(\bowtie\).
Continuum Size Size properties can be expressed by adapting constructions to remain triangle-free.

Maximality and the S5 Axiom

S5 Axiom: \(\Diamond\Box\varphi \rightarrow \varphi\)
Meaning "If something is possibly necessary, then it must already be true."
A graph satisfies this principle if it is "maximal" or "complete" with respect to its class—it already contains every structure that it could possibly be forced to contain in an extension.

The Two “Maximal" Graphs

The Random Graph (R)
  • Maximal in the general setting.
  • Contains every finite graph (including triangles).
  • Validates S5 for general modal graph theory.
The Henson Graph (\(H_3\))
  • Maximal in the triangle-free setting.
  • Contains every finite triangle-free graph.
  • Validates S5 for TF modal graph theory.

Why the Henson Graph is Different

The difference comes from the meaning of "possibility":

In the world of the Random Graph… It is always possible to add an edge that completes a triangle.
In the world of the Henson Graph… It is impossible to add an edge that completes a triangle.
The Takeaway: Restricting extensions changes the entire landscape of modal truths.

References

“The Graph is Connected” is Not First-Order Definable

Assume for contradiction Suppose there is a first-order sentence \(\psi\) in the language of graph theory such that for every graph \(G\), \[ G \models \psi \quad\text{if and only if }\quad G \text{ is connected.} \]
For each \(n \in \mathbb{N}\), let \(\psi_n\) be the sentence: “There exist two vertices with a path of length \(\le n\) between them.” Consider the set of sentences
\[ T \;=\; \{\psi\}\;\cup\;\{\neg\psi_n : n\in\mathbb{N}\}. \]
Idea: Compactness (finitely satisfiable \(\Rightarrow\) satisfiable)

Compactness Forces a Contradiction

Every finite subset is satisfiable Take any finite subset of \(T\). It contains \(\psi\) and only finitely many of the \(\psi_n\)’s, say up to some largest bound \(N\).

Let \(G\) be a path of length \(N+1\). Then \(G\) is connected, so \(G \models \psi\).

Also, the two endpoints of the line have distance \(N+1\), so in particular there is no path of length \(\le N\) between them, hence \(G \models \neg\psi_n\) for every \(n \le N\).
But the whole set \(T\) is impossible to satisfy If a graph satisfies \(\psi\), it is connected.

In a connected graph, for any two vertices \(x,y\), there is some finite path between them, hence \(\psi_{n}\) holds for some \(n\).

That contradicts having \(\neg\psi_n\) true for every \(n\).
Conclusion There no such sentence \(\psi\) that expresses connectedness in the first-order language of graphs.