A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete?
Proof it is in NP: Given the cliques of size k, I can verify if it they are the cliques of size k.
Proof of NP-hardness: If there is only one edge between them, how can I be sure that this is the edge I need for the reduction?
I'm trying to reduce from the k-clique problem as it seems to be the easiest choice.
I'm new to this so, if I'm wrong somewhere, please help me out !