Partial words are finite sequences over a finite alphabet that may contain some holes. A variant of the celebrated Fine–Wilf theorem shows the existence of a bound L=L(h,p,q) such that if a partial word of length at least L with h holes has periods p and q, then it also has period gcd(p,q). In this paper, we associate a graph with each p- and q-periodic word, and study two types of vertex connectivity on such a graph: modified degree connectivity and r-set connectivity where r=qmodp. As a result, we give an algorithm for computing L(h,p,q) in the general case and show how to use it to derive the closed formulas.