Problem

Source: 239 2019 J8

Tags: combinatorics



There are $n$ instruments in the laboratory, each two of them can be connected with a wire. Moreover, if four devices $A, B, C, D$, are such that wires of $AB$, $BC$ and $CD$ are connected but there is no connected pair between $CA$, $AD$ and $DB$, a collapse occurs. A professor invented a wiring diagram that does not collapse. Coming to the laboratory, he found that the collapse has not yet occurred, but the devices are connected not according to his scheme. Prove that he can implement his scheme, each time connecting or disconnecting a pair of devices, so that the collapse won’t happen anytime.