This question is from a Goldman Sachs Internship Test. The question was roughly as follows:

There are n places in a city, we need to connect each place to every other place in the city by roads (called complete day condition). The way we update edges(roads) is by selecting a node(place), upon which every pre-existing edge from that node will vanish and every possible edge that wasn't there in pre-existing edges (which just vanished) will appear. We can select any number of nodes, in any order. There were some pre-existing edges provided for every city. Task is to figure out if complete day condition will be met by some order of selection of nodes.
number of nodes : n <= 1000.

My idea was to make an array of n of bools, where the value represents the parity of the number of times a node is selected. If for some nodes x and y, sum of parity was even then the edge between the edge should exist if odd then edge shall not exist. I will start by assuming parity for first node and see if we can figure out parity of rest without contradiction. I wasn't able to code this.

Will this approach work? What is an optimal way to solver this problem.