Auto comment: topic has been updated by Ra1nWarden (previous revision, new revision, compare).

The graph looks like this (the numbers indicate the number of armies, just as in the problem statement, vertices with 0 armies are hostile).

  0---5
  
    7
    |
    3*
   / \
  3---2
   \ /
    0
 

The graph consists of two components. Note that for the first component, no movement can occur (we can not attack hostile vertices, and the vertex with 5 armies is otherwise isolated). This already gives us an upperbound of 5.

As for the second component. Note that from the vertex I marked with a *, we can move 1 army to the the other vertex with 3 armies, and 2 to the vertex with 2 armies. This creates a problem though: the *-vertex will have 0 armies. Because of this, we should first move some (anywhere from 1 to 6) armies from the 7-vertex to the *-vertex. This is allowed since as the problem statement says, we can do the movements one by one. The sequence thus is: move 1 army from the 7-vertex to the *-vertex; move 1 army from the *-vertex to the other 3-vertex; move 2 armies from the *-vertex to the 2-vertex.

The result is this:

  0---5
  
    6
    |
    1
   / \
  4---4
   \ /
    0
 

So this is a solution with ""strength"" 4. It should be easy to see this is optimal.