Let $\mathcal{P}_G$ be the family of all topologically mixing, but not exact self-maps of a topological graph $G$. It is proved that the infimum of topological entropies of maps from $\mathcal{P}_G$ is bounded from below by $(\log 3/ \Lambda(G))$, where $\Lambda(G)$ is a constant depending on the combinatorial structure of $G$. The exact value of the infimum on $\mathcal{P}_G$ is calculated for some families of graphs. The main tool is a refined version of the structure theorem for mixing graph maps. It also yields new proofs of some known results, including Blokh's theorem (topological mixing implies specification property for maps on graphs).
