Suppose you are given a clique C of size n with vertices x1, x2,..., xn. An edge (xi, xj) is said to generate C if {xi, xj} ? ( N(xi) ?N(xj) ) is exactly {x1, x2, ..., xn}, where N(xi) is the set of neighbor vertices of xi. Give an optimal algorithm to delete the least number of edges in C so that no leftover edges generate C. Note: Your solution should be O(n).
Definition of a Clique: A clique is an undirected graph G = (V, E) where V = {x1, x2,..., xn} and for any xi, xj ∈ V and i =? j, (xi, xj) ∈ E.