A note on maximal triangle-free graphs

We show that a maximal triangle-free graph on n vertices with minimum degree δ contains an independent set of 3δ ? n vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. © 1993 John Wiley & Sons, Inc.