A bowtie is a graph on an even number of vertices, say 2g, i…
A bowtie is a graph on an even number of vertices, say 2g, in which there are 2 disjoint cliques of size g with exactly one edge between the 2 cliques. Consider the Bowtie problem: Input: an undirected graph G=(V,E) and a nonnegative integer g. Output: two disjoint sets of vertices S and T such that their union is a bowtie of size 2g, if such graph exists. This is, S must be a clique on g vertices, T must be a clique in g vertices and exactly one edge connects the two sets. Show that the Bowtie problem is NP-complete.