PHOEG: an online tool for discovery and education in extremal graph theory
Sébastien Bonte, Gauvain Devillez, Valentin Dusollier, Hadrien Mélot[3mm] Computer Science Department - Algorithms Lab[-2mm] University of Mons, Mons, Belgium, [-2mm] Corresponding author: [email protected][3mm] · 2026
Read PHOEG: an online tool for discovery and education in extremal graph theory by Sébastien Bonte, Gauvain Devillez, Valentin Dusollier, Hadrien Mélot[3mm] Computer Science Department - Algorithms Lab[-2mm] University of Mons, Mons, Belgium, [-2mm] Corresponding author: [email protected][3mm] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-27242.txt.
Introduction
Bonte and co-authors present PHOEG, an exact online tool for extremal graph theory. The field hunts inequalities between graph invariants amid a flood of graphs. Most tools settle for rough or probabilistic answers to stay fast. PHOEG instead embeds graphs in a 2D invariant space and builds convex hulls exactly. Hull facets spell out inequalities, and vertices mark extremal graphs. Its library holds all non-isomorphic graphs up to order ten. Users can spot conjectures and counterexamples quickly. It is also used in university coursework.
Catalog record
| CREATOR | Sébastien Bonte, Gauvain Devillez, Valentin Dusollier, Hadrien Mélot[3mm] Computer Science Department - Algorithms Lab[-2mm] University of Mons, Mons, Belgium, [-2mm] Corresponding author: [email protected][3mm] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36169 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.27242
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
PHOEG: an online tool for discovery and education in extremal graph theory Sébastien Bonte, Gauvain Devillez, Valentin Dusollier, Hadrien Mélot[3mm] Computer Science Department - Algorithms Lab[-2mm] University of Mons, Mons, Belgium, [-2mm] Corresponding author: [email protected][3mm] Abstract Abstract. Extremal Graph Theory heavily relies on exploring bounds and inequalities between graph invariants, a task complicated by the rapid combinatorial explosion of graphs. Various tools have been developed to assist researchers in navigating this complexity, yet they typically rely on heuristic, probabilistic, or non-exhaustive methods, trading exactness for scalability. PHOEG takes a different stance: rather than approximating, it commits to an exact approach. PHOEG is an interactive online tool ( https://phoeg.umons.ac.be ) designed to assist researchers and educators in graph theory. Building upon the exact geometrical approach of its predecessor, GraPHedron, PHOEG embeds graphs into a two-dimensional invariant space and computes their convex hull, where facets represent inequalities and vertices correspond to extremal graphs. PHOEG modernizes and expands this approach by offering a comprehensive web interface and API, backed by an extensive database of pairwise non-isomorphic graphs including all graphs up to order 10. Users can intuitively define invariant spaces by selecting a pair of invariants, apply constraints and colorations, visualize resulting convex polytopes, and seamlessly inspect the corresponding drawn graphs. In this paper, we detail the software architecture and new web-based features of PHOEG. Furthermore, we demonstrate its practical value in two primary contexts: in research, by illustrating its ability to quickly identify conjectures or counterexamples to conjectures, and in education, by detailing its integration into university-level coursework to foster student discovery of classical graph theory principles. Finally, this paper serves as a brief survey of the extremal results and conjectures established over the past two decades using this geometric approach. Keywords: chemical graphs, degree-based topological index, extremal graphs. 1 Introduction Extremal Graph Theory studies bounds on graph invariants, which are values preserved under isomorphism, such as order, size, chromatic number, or average distance. These problems are typically subject to constraints like fixing the value of some invariants. Finding these bounds, and the extremal graphs that realize them, is challenging: the sheer number of graphs grows extremely rapidly, exceeding a hundred billion for graphs of order 12 alone. To tackle this complexity, several computational tools have been developed over the years. Early efforts include Graph by Cvetkovic et al. [ 13 ] and its successor newGRAPH by Brankov et al. [ 32 ] . Graffiti [ 19 ] , developed by Fajtlowicz in 1988, used heuristics and pre-computed data to generate thousands of conjectures automatically. AutoGraphiX [ 9 ] , by Caporossi and Hansen in 2000, applied variable neighborhood search to identify extremal graph candidates. Concurrently, databases like House of Graphs [ 5 , 12 , 15 ] emerged, offering a searchable repository of interesting graphs allowing researchers to query specific invariant values or search for counterexamples. These tools have proven valuable, but they share a common characteristic: they are not exhaustive. Whether through heuristics, sampling, or selective search, they sacrifice exactness for scalability. GraPHedron [ 29 ] , introduced by Mélot in 2008, took a deliberately different stance: rather than approximating, it committed to an exact approach. It embedded all graphs up to a given order into an invariant space and computed their convex hull, interpreting facets as inequalities between invariants and vertices as extremal graphs. Historically, GraPHedron was instrumental in the early days of House of Graphs, as it was used to compute and introduce the very first graphs into the database. However, unlike some of its contemporaries, GraPHedron itself was never updated — motivating the development of its successor, PHOEG (a recursive acronym for PHOEG Helps to Obtain Extremal Graphs). First introduced in 2019 [ 16 ] , PHOEG embraces this same goal of exactness. The trade-off is explicit and assumed: PHOEG operates on all pairwise non-isomorphic graphs up to order 10, the practical frontier imposed by combinatorial growth. It combines a database of graphs enabling fast queries and computations with a proof-assistance module called TransProof. Since its initial release, we have significantly expanded PHOEG to democratize its access ( https://phoeg.umons.ac.be ). Through extensive use in both research and educational settings, we refined the tool and developed a comprehensive web interface and API. This paper presents these modernizations and illustrates them through a detailed walkthrough of the platform. Section 2 briefly recalls the underlying geometrical approach PHOEG is built on. Section 3 details the new web interface functionalities and the technologies used to develop them. Section 4 serves as a mini-survey of the extremal results obtained over the years using this geometric approach, and illustrates PHOEG’s practical applications in research through concrete examples. Section 5 details its use in educational settings. Finally, in Section 6 we conclude and discuss future directions. 2 Geometrical approach This section explains the geometrical approach underlying PHOEG and introduced in GraPHedron [ 29 ] . We first introduce a few basic mathematical definitions necessary to understand this methodology. Throughout this paper, we consider simple, undirected graphs G=(V,E) , where V is the set of vertices and E is the set of edges. The order of a graph G is the number of its vertices, denoted by n=|V| , and its size is the number of its edges, denoted by m=|E| . The degree of a vertex v\in V , denoted by d(v) , is the number of edges incident to v . For standard notations of graph theory that are not defined here, we refer the reader to Diestel [ 18 ] . As stated by Hansen et al. [ 20 ] , many results in extremal graph theory are expressed in terms of inequalities between graph invariants. This observation guided the design of GraPHedron and remains the core principle in PHOEG. The geometrical approach used in PHOEG places simple, undirected graphs into a two-dimensional space where each dimension corresponds to a specific graph invariant. Each graph of a given order is represented as a point whose coordinates are the values of the two chosen invariants evaluated on that graph. It is important to note that a single point in this space may represent several non-isomorphic graphs, as they can share the exact same values for the chosen pair of invariants. The convex hull of all these points forms a convex polytope. Recall that the convex hull of a finite set of points in the plane is the smallest convex set enclosing them, and that its boundary consists of facets , the edges of the polygon in two dimensions. Consequently, each facet of this convex polytope corresponds to a linear inequality between the invariants (typically of the form aX+bY\leq c ), and the vertices represent the extremal graphs that tightly achieve these bounds. An example of such a polytope is shown in Figure 1 . The two invariants defining the space in this example are the chromatic number (the minimum number of colors needed to color the vertices such that no two adjacent vertices share the same color) for the X -axis and the clique number (the number of vertices in the largest complete subgraph) for the Y -axis. The points plotted represent all graphs of order 7. To illustrate that a single point