We present a library for graph theory in Coq/Ssreflect. This library covers various notions on simple graphs, directed graphs, and multigraphs. We use it to formalize several results from the literature: Menger's theorem, the excluded-minor characterization of treewidth-two graphs, and a correspondence between multigraphs of treewidth at most two and terms of certain algebras. Graph Theory in Coq: Minors, Treewidth, and Isomorphisms Further, invalid proofs of related claims have already been published in the literature (see [23] ). Our initial motivation for this work [10] was to formalize †: not only will this give us assurance about the validity of the proof in [23], it will also allow for the development of automation tactics for certain algebraic theories (e.g., 2p-algebra, allegories [16, 29] ). We present three important steps towards the formalization of this result: 1. graphs form a 2p-algebra; 2. graphs of treewidth at most two form a subalgebra; 3. every graph excluding K 4 as a minor can be represented by a term. These three steps cover different situations which are frequently encountered when reasoning about graphs. The first point requires us to define several constructions on graphs (e.g., disjoint unions and quotients), and to establish a number of isomorphisms. The second point requires us to show that these constructions preserve treewidth. The third point requires us to analyze the structure of K 4 -free graphs in order to decompose them recursively; for this we again make use of Menger's theorem. The final step for † consists in proving that terms denoting isomorphic graphs are equivalent modulo the axioms of 2p-algebras. We formalized this step during the reviewing process of this article; the formalization is based on the proof in [11] rather than the one in [23] which we had set out to formalize in [10] . Proving † required us to introduce new techniques which we describe in [12] . We do not describe this work in the present article. Outline We discuss our representation choices for directed graphs, simple graphs, and paths in Sect. 3. Then we proceed to proving Menger's Theorem (Sect. 4). We define tree decompositions and minors in Sects. 5 and 6, so that we can prove the minor-exclusion theorem for treewidth two in Sect. 7. We end the presentation of the general purpose part of the library by defining labeled multigraphs in Sect. 8, together with the associated notion of isomorphism. In the remaining sections we apply our library to 2p-algebra: We define a 2p-algebra of graphs and show that treewidth at most two graphs form a subalgebra (Sect. 9). We then prove a number of lemmas for analyzing the structure of K 4 -free graphs (Sect. 10), which make it possible to recursively extract terms from connected K 4 -free graphs (Sect. 11). We finally extend this extraction function to arbitrary K 4 -free graphs in Sect. 12. The Coq library accompanying this paper [9] evolved significantly since [10] and continues to evolve, hence the different structure of the present paper: the main contribution is the graph library itself, rather than the application to 2p-algebras. The most noticeable improvement is that we prove Menger's Theorem and use it both to provide a direct proof of the minor-exclusion theorem for treewidth two, and to simplify the recursive analysis of K 4 -free graphs. (Lemma 10.8 follows easily with Menger's Theorem, while it was requiring a long series of ad-hoc lemmas in [10] .) We also prove that graphs satisfy the laws of 2p-algebra (Lemmas 9.2 and 9.3). This required us develop techniques for dealing with the complicated isomorphisms arising with nested quotients and disjoint unions in a compositional manner (Lemma 8.7).
Doczkal and Pous REF develop a mechanization of graph theory in Coq, including simple graphs, digraphs, and their properties.
Graph Theory in Coq: Minors, Treewidth, and Isomorphisms
Journal of Automated Reasoning
Journal of Automated Reasoning
Mathematics