I have a problem starting this task: An n-vertex graph is a scorpion if it has a vertex of degree 1(the sting) connected to a vertex of degree two (the tail) connected a vertex of degree n-2 (the body) connected to the other n-3 (the feet). Some of the feet may be connected to other feet. Design an algorithm that decides whether a given drawing represents a scorpion. . I should make adjacency matrix and then try to search basically for sting which has only one connection with tail and do the same thing with tail and body...?
You start by determining the degree of each vertex (from adjacency matrix or adjacency lists or any other way this is possible), then choose the one vertex of degree n-2 as body center (there is just one such vertex if n > 4 and your graph is a spider, also there should be no vertex of degree n-1). The sting head is the one vertex that the body center is not adjacent to if the graph is a spider. Check the sting head has degree 1. And then you check that the sting head is connected to a vertex of degree 2 (i.e. the sting-tail articulation). If n <= 4, you only get degenerated spiders (for n=4, the spider has one leg, for n=3 the spider has no legs, for n=2, n=1 or n=0 you can't have a spider).