A modal logic for finite graphs
In this work we present a proof theory for a modal logic
based on [BMdR96, BM94], that is sound and complete with respect to finite
directed graphs. We prove soundness and completeness using techniques used in
Dynamic Logic [Gol92, BdRV94] and in [BMdR96, BM94]. We extend the language
to a new modal system and show that it is sound and complete with respect to
the class of undirected finite graphs. Finally, we investigate if some well
known properties of undirected graphs are modally definable or not (e.g.
planarity, coloring, Eulerian graph and etc.
Mario R.F. Benevides