This is an old revision of the document!

Graphs as Interpretations

Directed graph is is given by a set of vertices $V$ and a set of edges $E \subseteq V \times V$ . Graph is therefore specified by an interpretation $I = (V,\alpha)$ in languge ${\cal L} = \{edge\}$ with $\alpha(edge) = E$ .

Example: $D = \{1,2,3,4\}$ , $\alpha(edge) = \{ (1,2), (2,3), (1,3), (3,4) \}$ .

For a class of graph properties we can write down a formula $F$ such that property holds for graph iff $F$ is true in the interpretation $I$ representing the graph.

No self-loops: \[

  \forall x.\ \lnot edge(x,x)

Undirected graph: \[

 \forall x.\ edge(x,y) \rightarrow edge(y,x)

Tournament: \[

 \forall x, y.\ (edge(x,y) \lor edge(y,x)) \land \lnot (edge(x,y) \land edge(y,x))

Note: there is no formula $F$ in this language ${\cal L} = \{edge\}$ that characterizes property “graph has no cycles”. All properties expressed in first-order logic on graphs are “local”.

Many more properties become expressible if we take as domain $D$ the set of all subsets of $V$ and allow set operations in our language.