The sizes of Jordan blocks of regular matrix pencils are investigated by means of a one-to-one correspondence between a matrix pencil \((\lambda E+\mu A)\) and a weighted digraph \(G(E,A)\). Based on the relationship between determinantal divisors of a pencil and spanning-cycle families of the associated digraph \(G(E,A)\), the Jordan-block-size structure is determined graph-theoretically. For classes of structurally equivalent matrix pencils defined by a pair of structure matrices \([E,A]\), the generic Jordan block sizes corresponding to the characteristic roots at zero and at infinity can be obtained from the unweighted digraph \(G([E],[A])\). Eigenvalues of matrices are discussed as special cases.