Problem

Source: Stars of Mathematics 2007, Day 2, Problem 2

Tags: graph theory, discrete maths



Let be a structure formed by $ n\ge 4 $ points in space, four by four noncoplanar, and two by two connected by a wire. If we cut the $ n-1 $ wires that connect a point to the others, the remaining point is said to be isolated. The structure is said to be disconnected if there are at least two points for which there isn´t a chain of wires connecting them. So, initially, it´s not disconnected. $ \text{(1)} $ Prove that, by cutting a number smaller or equal with $ n-2, $ the structure won´t become disconnected. $ \text{(2)} $ Determine the minimum number of wires that needs to be cut so that the remaining structure is disconnected, yet every point, not isloated.