When evaluating 2-way constrained covering arrays, the minimum sizes given by the existing methods are too large because the constraints are ignored. In order to obtain more accurate minimum sizes of 2-way constrained covering arrays and evaluate the 2-way constrained covering arrays generated by existing algorithms, a forbidden edge decomposing method was proposed to promote lower bounds of the minimum sizes of 2-way constrained covering arrays in this study. The graphs that describe the input configurations of the systems under test were decomposed into two subgraphs. Through calculating the sizes of the sub constrained covering arrays which cover all the vertices in the two subgraphs and the number of the remaining value combinations to be covered, the minimum sizes of the 2-way constrained covering arrays were promoted compared with the number of the value combinations to be covered. The lower bounds of the minimum sizes obtained from the proposed method were closer to the real values. If the sizes of the 2-way constrained covering arrays are less than the lower bounds of the minimum sizes, then it is impossible for them to exist. The proposed experimental method applied the forbidden edge decomposing method to the existing systems under test, then obtained the lower bounds of the minimum sizes of 2-way constrained covering arrays, and compared the lower bounds of the minimum sizes with the sizes of the 2-way constrained covering arrays given by the generation algorithms. The experimental results show that the lower bounds of the minimum sizes given by the forbidden edge decomposing method can be used to evaluate the 2-way constrained covering arrays generated by the existing algorithms, and are helpful to determine their existence.