< Back to previous view
Sign in

Maximal triangle-free graphs

Last update: 15 Dec 2020  | Contains: 197396 graphs

A triangle-free graph is an undirected connected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4 (or 0), graphs with no induced 3-cycle, or locally independent graphs.
In order to determine properties of all triangle-free graphs, it often suffices to investigate maximal triangle-free graphs. These are triangle-free graphs for which the insertion of any further edges would create a triangle. The following collection was calculated by the House of Graphs (source) and lists maximal triangle-free graphs on up to 17 vertices.

OEIS: A216783

Collection comments

Only signed in users can post comments. Sign in here
Don't have an account yet? Register here