Thursday, February 9, 2012
Identify if a given graph is a scorpion or not.
A scorpion is an undirected graph with 3 special vertices: the sting, the tail, and the body. The sting has degree one and is connected to the tail. The tail has degree two and is connected to the sting and the body. The body has degree n – 2 and is connected to all vertices except the sting. The other vertices may be arbitrarily connected with each other. Identify if a given graph is a scorpion or not.