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.
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