Shortest Path Length as mathematical function/expression I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities.

*

*The degree of any node should be at least 3.

*The shortest path length between any two nodes should be at most 5.

I have an adjacency matrix $X$.

$Xij = 1$, if $i$ and $j$ are directly connected,
$0$ otherwise

Now, I have expressed constraint 1 as

$\sum_j X_{ij} \ge 3$

that is for every node $i$, the row-wise sum should be at least $3$
I don't know how to express the constraint 2 in terms of $X_{ij}$.
if $f(X)$ is the shortest path length, $f(X) \le 5$ is the constraint. But what is $f(X)$, the mathematical function for shortest path length ?


gt6989b's comment goes most of the way towards solving your problem. The number of paths from $i$ to $j$ of length $m$ is $(X^m)_{ij}$, so the number of paths from $i$ to $j$ of length at most $m$ is $\left(\sum_{k=0}^mX^k\right)_{ij}$. In your case, all these entries should be positive for $m=5$, so you want
$$
\left(\sum_{k=0}^5X^k\right)_{ij}=\left(\frac{1-X^6}{1-X}\right)_{ij}\gt0\quad\text{for all}\quad1\le i,j\le n\;
$$
(where the expression in the middle is defined unless the adjacency matrix has an eigenvalue $1$). 
