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.
Illustrating Valid vs. Invalid Extensions
Base Graph (TF)
Valid Extension Remains Triangle-Free
Invalid Extension Triangle Created (\(c \sim d\))
Why Expressing Connectivity is a Big Deal
A Classic Limitation
You cannot write a first-order graph formula that is true iff two vertices are connected by a path.
The Power of Modal Logic
Modal logic quantifies over extensions, enabling a definition of path-connectedness.
The Modal Formula for Connectivity (General Case)
Hamkins & Wołoszyn
\[
\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 is trying to define
Think of the displayed formula as a predicate \(\mathrm{Conn}(x,y)\) meaning:
“\(x\) and \(y\) are connected by a path.”
Then a modal definition of graph connectedness is the single sentence:
\(\forall x\,\forall y\,\mathrm{Conn}(x,y)\).
In Plain English
Necessarily, for any newly added node \(c\): if \(c\) attaches to \(x\) and its adjacency is forced to be “closed” under one-step moves,
then \(c\) must also attach to \(y\).
The Problem: Direct Connections Can Create Triangles
The Issue
The original formula uses direct connections like \(c \sim x\). In triangle-free extensions, this can force a forbidden triangle immediately.
The Solution: A Triangle-Free Proxy Connection
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).
\]
The “private witness” condition prevents \(z\) from participating elsewhere, so \(\bowtie\) behaves like a dedicated two-step connector.
The Adapted Formula for Connectivity (Triangle-Free)
Replace direct adjacency in the extension-behavior 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]
\]
In Plain English
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 / Countability
Expressible via special “witness” configurations built using \(\bowtie\).
Continuum Size
Size properties can be expressed by adapting constructions to remain triangle-free.