We give a formal and constructive proof in Coq/Ssreflect of the known result that the graphs of treewidth two are exactly those that do not admit K4 as a minor. This result is a milestone towards a formal proof of the recent result that isomorphism of treewidth-two graphs can be finitely axiomatized. The proof is based on a function extracting terms from K4-free graphs in such a way that the interpretation of an extracted term yields a treewidth-two graph isomorphic to the original graph. Amongst the open problems related to treewidth, there is the question of finding finite axiomatisations of isomorphism for graphs of a given treewidth [5, page 118]. This question was recently answered positively for treewidth two [14]: K 4 -free graphs form the free 2p-algebra, where 2p-algebras are algebraic structures characterized by twelve equational axioms. The proof is rather technical; it builds on a precise analysis of the structure of K 4 -free graphs and contains the specific form of the graph minor theorem for treewidth two which we present here. Further, invalid proofs of related claims have already been published in the literature (see [14] ). Our long term goal is to formalize ( †): not only will this give us assurance about the validity of the proof in [14] , it will also allow for the development of automation tactics for certain algebraic theories (e.g., 2p-algebra, allegories [11] ). The Coq development accompanying the present paper [7] is a milestone for this project. Independently from the aforementioned specific objective, formalizing the graph minor theorem for treewidth two requires us to develop a general Coq library for graph theory which should also be useful in other contexts. This library currently includes basic notions like paths, trees, subgraphs, and isomorphisms and also a few more advanced ones: minors, tree decompositions, and checkpoints (a variant of cut vertices). We had to design this library from scratch. Indeed, there are very few formalizations of graph theory results in Coq, and none of them were applicable. Gonthier's formal proof of the Four-Color Theorem [12] is certainly the most advanced, but it restricts (by design) to planar graphs so that it cannot be used as a starting point for graph theory in the large. Similarly, Durfourd and Bertot's study of Delaunay triangulation [9] employs a notion of graphs based on hypermaps embedded in a plane. There are more formalizations in other interactive theorem provers. For instance, planar graphs were formalized in Isabelle/HOL for the Flyspeck project [16] . Noschinski recently developed a library for both simple and multi-graphs in Isabelle/HOL [17] . Chou developed a large part of undirected graph theory in HOL [2]. Euler's theorem was formalized in Mizar [15] . To the best of our knowledge, the theory of minors and tree decompositions was never formalized.
In a recent work REF aimed towards formalizing the graph minor theorem for treewidth two Doczkal et al. developed a general library for graphs using the Coq Proof Assistant.
A Formal Proof of the Minor-Exclusion Property for Treewidth-Two Graphs
ITP
Computer Science