circular-arc graphs. The Moser spindle, a seven-vertex graph used to provide a lower bound for the chromatic number of the plane, is claw-free. The graphs of several polyhedra and polytopes are claw-free, including the graph of the tetrahedron and more generally of any simplex (a complete graph), the graph of the octahedron and more generally of any cross polytope (isomorphic to the cocktail party graph formed by removing a perfect matching from a complete graph), the graph of the regular icosahedron, and the graph of the 16-cell. The Schläfli graph, a strongly regular graph with 27 vertices, is claw-free. Recognition It is straightforward to verify that a given graph with n vertices and m edges is claw-free in time O(n4), by testing each 4-tuple of vertices to determine whether they induce a claw. With more efficiency, and greater complication, one can test whether a graph is claw-free by checking, for each vertex of the graph, that the complement graph of its neighbors does not contain a triangle. A graph contains a triangle if and only if the cube of its adjacency matrix contains a nonzero diagonal element, so finding a triangle may be performed in the same asymptotic time bound as n × n matrix multiplication. Therefore, using the Coppersmith–Winograd algorithm, the total time for this claw-free recognition algorithm would be O(n3.376). observe that in any claw-free graph, each vertex has at most 2 neighbors; for otherwise by Turán's theorem the neighbors of the vertex would not have enough remaining edges to form the complement of a triangle-free graph. This observation allows the check of each neighborhood in the fast matrix multiplication based algorithm outlined above to be performed in the same asymptotic time bound as 2 × 2 matrix multiplication, or faster for vertices with even lower degrees. The worst case for this algorithm occurs when Ω() vertices have Ω() neighbors each, and the remaining vertices have few neighbors, so its total time is O(m3.376/2) = O(m1.688). Enumeration Because claw-free graphs include complements of triangle-free graphs, the number of claw-free graphs on n vertices grows at least as quickly as the number of triangle-free graphs, exponentially in the square of n. The numbers of connected claw-free graphs on n nodes, for n = 1, 2, ... are 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... . If the graphs are allowed to be disconnected, the