Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.
Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.
Consider the LP:
$\max \lambda$
s.t: $p_i + \lambda \le p_j + c_{i,j}$ where $(i,j)\in \mathcal A$.
I've shown:
The LP is feasible.
If $(\lambda,p)$ is a feasible solution then the directed cycle mean cost of every directed cycle is at least $\lambda$.
The LP has an optimal solution (doesn't contain a line and $\lambda$ can't be greater than the maximum cost).
Now, I want to show given an optimal solution to the LP, it can be used to construct a directed cycle with minimal directed cycle mean cost.
I really don't have a clue on how to proceed. I don't see how an optimal solution give me the required information ?
Let $(\lambda,p)$ be an optimal solution of LP.
Let $i_0,i_1,...,i_n$ be a sequence of nodes in a cycle (i.e. $(i_k,i_k+1)\in A$ and $(i_n,i_0)\in A$).
Since $(\lambda,p)$ is a solution of LP you know that for every $k$: $$p_k+\lambda\leq p_{k+1}+c_{k,k+1}$$ and $p_n+\lambda\leq p_{0}+c_{n,0}$.
Hence by doing the sum on the cycle: $$\sum_{k=0}^n (p_k+\lambda)\leq \sum_{k=0}^{n-1}( p_{k+1}+c_{k,k+1}) + p_{0}+c_{n,0} $$ hence $$\sum_{k=0}^n p_k+(n+1)\lambda\leq \sum_{k=1}^{n} (p_{k}+c_{k-1,k}) + p_{0}+c_{n,0} $$ hence $$(n+1)\lambda\leq\sum_{k=0}^{n-1}c_{k,k+1}+c_{n,0}$$ Hence $\lambda\leq$ cycle mean cost. And this for any cycle.
Now you have to think of what happen in the case of equality, and use the fact that the solution is optimal.
I hope this helps you. If you have any further questions, please ask.
Wec.
Note that the nodes not included in any cycles does not play any role in bounding $\lambda$ since you can increase the $p$ arbitrarily for those nodes.
[EDIT]
For your second question: Consider the graph $G'$ where you removed all the nodes that don't take part in a cycle. Find an optimal solution for LP in $G'$. From this solution you can easily find a solution for LP in $G$ by setting the right $p_i$ to the node you removed (set $p_j=p_i+\lambda$ for all the new node where $(i,j)\in A$ and iterate until you find a fix point). This solution is also optimal for $G$, because if you find a better solution for $G$ then the restriction to $G$ is also a solution.
For the first question: From what's above you can (without loss of generality) consider a graph in which every nodes are part of a cycle. The intuition behind "there must be an equality for a cycle" is that if for all cylces the inequality is strict then for all nodes i,j such that $p_i+\lambda=p_j+c{i,j}$ you can increase a bit the $p_j$ and "push" the difference along all cycle until it's absorbed by the cycle. And, once you don't have any equality $p_i+\lambda=p_j+c{i,j}$ you can increase a bit the $\lambda$ hence find a better solution.
I hope it's clear. Ask if it's not ...