Find the Prime Number

Hint: find the maximum and minimum number of red edges needed to construct a spanning tree and check if there exists some prime numbers between them.