Gallais Path Conjecture

Gallai's Conjecture, formulated by Tibor Gallai in 1968, is a foundational problem in graph theory concerning the decomposition of graphs into paths. The conjecture states that:

Conjecture (Gallai, 1968) Every connected graph with $n$ vertices can have its edges decomposed into at most $\frac{n+1}{2}$ paths.

This conjecture highlights a deep connection between the structure of a graph and its decomposition into a minimal number of paths. Over the years, Gallai's Conjecture has been verified for specific classes of graphs, such as:

Lovasz proved that the conjecture holds for simple, connected graphs where all vertices have an odd degree. Note that in this case, the bound is tight, i.e. the number of paths in the decomposition is exactly $\frac{n+1}{2}$. Other results regarding the degree of a graph were later proven, for example by Favaron et al. who showed that the conjecture holds for 2-regular and 4-regular graphs and Botler et al. who generalized this to graphs with maximum degree at most 5.

Results regarding induced subgraphs of $G$ were also proven, for example by Pyber who showed that the conjecture holds for graphs where the induced graph by the vertices of even degree is a forest and by Fan who then generalized this to triangle free graphs of maximum degree at most 3.

Despite these advancements, the conjecture remains unproven in its full generality, presenting an enduring challenge in combinatorics.

In this article, we will verify Gallai's Conjecture for all connected graphs with at most 10 vertices. This result extends the range of graphs for which the conjecture is known to hold and provides computational evidence supporting its validity. Through systematic enumeration and verification of edge decompositions, we establish that no counterexamples exist for graphs of this size.

In the following, we formulate the problem as an integer linear program (ILP). First of all, we introduce some notations.

Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. We use $V = \{1, 2, \ldots, n\}$ to denote the vertices of $G$. For each edge $e \in E$, we denote by $u$ and $v$ the two vertices that it connects. We denote by $P$ the set of all possible paths in $G$. The total number of paths is denoted by $k$ and is given by the conjectured upper bound $\frac{n+1}{2}$.

Our aim is to solve the ILP using python and gurobi. We start by importing the necessary libraries and setting up the model.

from gurobipy import GRB, model

model = Model("Gallai's Path Conjecture")

We introduce a binary variable $x_{e, p}$ for each edge $e \in E$ and each path $p \in P$. The variable $x_{e, p}$ is set to 1 if edge $e$ is used in path $p$, and 0 otherwise.

x = model.addVars([(e[0], e[1], p) for e in edges for p in range(k)], vtype=GRB.BINARY, name="x")
z = model.addVars(vertices, range(k), vtype=GRB.BINARY, name="z")
y = model.addVars(range(k), vtype=GRB.BINARY, name="y")

With these variables, we are able to define the objective function. We aim to minimize the number of paths used, which is equivalent to minimizing the sum of the $y_p$ variables.

model.setObjective(quicksum(y[p] for p in range(k)), GRB.MINIMIZE)

Now, we need to add the constraints to the model. The first constraint is that each edge must be used in exactly one path.

for e in edges:
    model.addConstr(sum(x[e[0], e[1], p] for p in range(k)) >= 1, 
                   name=f"edge_cover_{e[0]}_{e[1]}")

The next constraints ensure that the paths are valid. First, the edge variables set the variables of the incident vertices to 1 whenever the edge is used in a path.

for e in edges:
    u, v = e
    for p in range(k):
        model.addConstr(x[u, v, p] <= z[u, p], name=f"path_cont1_{u}_{v}_{p}")
        model.addConstr(x[u, v, p] <= z[v, p], name=f"path_cont2_{u}_{v}_{p}")

Furthermore, the degree of each vertex in a path is at most 2.

for v in vertices:
    for p in range(k):
        model.addConstr(
            sum(x[u, v1, p] for u, v1 in edges if v1 == v) + 
            sum(x[v1, u, p] for v1, u in edges if v1 == v) <= 2 * z[v, p],
            name=f"vertex_degree_{v}_{p}")

We also need to ensure that the paths are not a cycle.

for p in range(k):
    model.addConstr(sum(x[u, v, p] for u, v in edges) <= len(vertices) - 1, name=f"path_not_cycle_{p}")

Finally, we count the number of paths used.

for e in edges:
    for p in range(k):
        model.addConstr(x[e[0], e[1], p] <= y[p], name=f"path_usage_{e[0]}_{e[1]}_{p}")

This concludes the formulation of the ILP. We can now solve it using gurobi.

model.optimize()

Results

coming soon...