Akbari et al.’s edge-path matrix Conjectures 1 and 2

Let $G$ be a graph of order $n$ , and let $EP(G)=(p_{ij})$ be its edge-path matrix, where $p_{ij}$ is the maximum number of pairwise edge-disjoint paths between distinct vertices $v_i$ and $v_j$ , and $p_{ii}=0$ . Conjecture 1. For every positive integer $q$ , if $p_{ij}\leq q$ for all $i,j$ , then $|E(G)|\leq \frac{(q+1)(n-1)}{2}$ . Conjecture 2. The graph $G$ is Eulerian if and only if every entry of $EP(G)$ is even; that is, $G$ is Eulerian if and only if $p_{ij}\equiv 0\pmod 2$ for all $i,j$ .

Progress summary

Solved

A 2026 preprint claims to settle both conjectures, but the claim remains unverified.

Akbari et al. posed Conjecture 1 in 2022, asserting an upper bound on the number of edges from bounded pairwise edge-connectivity. Conjecture 2 asserts that a simple graph is Eulerian exactly when every entry of its edge-path matrix is even.

Known results

Conjecture 1 was proved in the special case $k=2$ , with the relevant graphs decomposing into cycle blocks (Akbari et al., 2022).

August 2026 preprint

“Two conjectures on graphs and their edge-path matrices” claims a general proof of Conjecture 1, including $|E(G)|\leq (q+1)(n-1)/2$ , and a proof of Conjecture 2 via Euler’s characterization and inclusion–exclusion. No independent verification, referee report, correction, or retraction is reported.

Current status (as of August 2026): Both conjectures have a claimed preprint proof, but neither is independently verified in the available record.

Sources

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Two conjectures on graphs and their edge-path matrices — arXiv — Metsidik, Metrose, Jin, Xian'an

graph-theory spectral-graph-theory

2 days ago