How to make a graph four-connected (Q1300060)

Solutions are given for two cases of the extremal version of the augmentation problem, which may be stated thus: given a triple \((n,k,l)\) of positive integers, what is the minimum number of new edges needed to be added to a \(k\)-connected graph on \(n\) vertices in order that the resulting augmented graph be \(l\)-connected? Theorem 3: If \(k=2\), \(n\geq 5\), and \(l=4\), then some set of \(n\) (or fewer) edges is always sufficient. If the graph \(G\) on \(n\) vertices is \((k-1)\)-connected and \((k-1)\)-valent, then clearly \(\lceil n/2\rceil\) edges are necessary to make \(G\) \(k\)-connected. It is conjectured that \(\lceil n/2\rceil\) is also sufficient whenever \(3\leq k\leq(n+1)/2\). This conjecture is proved (Theorem 4) for \(k=3, 4\) except when \(G=K_{3,3}\).