Lobsters

Lobsters are to caterpillars what caterpillars are to paths. In SAT-style terminology, lobster : caterpillar :: caterpillar : path. That is, a graph is a lobster if removing all degree-1 vertices results in a caterpillar. The smallest lobster that is not a caterpillar has 7 vertices. Removing all degree-1 vertices from the smallest lobster results in the smallest caterpillar, which also known as "the claw". I first heard about lobster graphs when reading about the Ringel-Kotzig conjecture in 1993. The conjecture is that all trees are "graceful", or more formally, that all trees admit a graceful labeling. A labeling of an n-vertex tree is graceful if the vertices can be numbered from 1 to n, so that when all the edges are labeled with the absolute difference of the labels of their endpoints, the list of edge labels covers all the numbers from 1 to n-1. This is one of those conjectures that everybody believes are true, but which are still difficult to prove. One class of trees for which the conjecture is proven true is the class of lobsters with perfect matching.