VULNERABILITY IN GRAPHS OF DIAMETER 4

The analogue of Menger's Theorem on connectivity has been investigated for graphs of low diameter in which the removal of a set of lines inc reases the diameter. When the diameter is at most three, such a theore m has been proven already. Also, examples have been constructed to sho w that the result does not always hold for graphs of diameter four or more. The line persistence of a graph is the minimum number of lines w hich must be removed to increase its diameter. Our present purpose is to characterize graphs of diameter four having two as the line persist ence.