  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).
