# Check if two vertices of a graph are connected with an MILP constraint

I have a mixed-integer linear program (MILP) that needs to select some edges from a graph according to some metrics.

One constraint that I'd like to enforce is that two given nodes have to be connected (i.e. there must exist a path between them).

looking at the adjacency matrix I know that one can find the shortest path or even all the possible path using some algorithms like breadth first search and even Dijkstra.

My question is: given that I do not want to know the path, can I formulate this ''path existence/connectivity problem'' as a constraint for a MILP problem?

The best idea I had was to compute all the paths connecting the two vertices offline and force the selection of at least one of those. Which would work, but it's something really inelegant.

Let $y_j$ be real variables indexed by the nodes of your graph, with $y_a = 0$ and constraints $y_j = y_k$ if $(j,k)$ is an edge. Then nodes $a$ and $b$ are connected iff this implies $y_b = 0$. Thus if you impose an upper bound of $1$ to keep things finite, and maximize $y_b$, an optimal solution has $y_b = 0$ if they are connected and $1$ if they are not.