An undirected bipartite graph G = (L, R, E) has two disjoint set of vertices L and R, and for every edge e ∈ E, one endpoint must be in L and another in R. We call a pair of distinct vertices u, v ∈ L

An undirected bipartite graph G = (L, R, E) has two disjoint set of vertices L and R, and for every edge e ∈ E, one endpoint must be in L and another in R. We call a pair of distinct vertices u, v ∈ L siblings if there exists a vertex r ∈ R such that both the edges (u, r) and (v, r) are present (in E). A subset F ⊆ L is said to be a family if for all the distinct u, v ∈ F, u and v are siblings. Now, consider the following problem: 

Given an undirected bipartite graph G = (L, R, E) and a positive integer k, decide whether there is a family F ⊆ L of size at least k. Show that the above problem is NP-complete. 

(You may show a reduction from any of the NP complete problems introduced in the lectures/tutorials, more specifically, Circuit Satisfiability, CNF SAT, 3-SAT, Vertex Cover, Independent Set, Max-Clique, Hamiltonian Cycle, Traveling Sales Person Problem.) [Hint: Try a reduction from the Max-Clique problem.]