1 | initial version |

Your loop `for g in graphs(i):`

iterates over all graphs of size `i`

, which is abig waste of time. The `graphs()`

generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter *during* the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.

Here, the property P is "being triangle-free and having chromatic number at most 3", which is stable by edge removal.

Hence `graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3)`

will generate all graphs of size `n`

with that property, see `graphs?`

for more details.

So, here is a possible way to construct the maximal graphs you are looking for:

```
def maximal_graphs(n):
mg = []
for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
maximal=True
for e in G.complement().edges():
H = copy(G)
H.add_edge(e)
if H.is_triangle_free() and H.chromatic_number() <= 3:
maximal=False
break
if maximal:
mg.append(G)
return mg
```

You can use that function to count the graphs you ar looking for:

```
sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]
```

You can then search in the OEIS, in case something is known about such sequence:

```
sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.
sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)
```

Unfortunately, the next term differs:

```
sage: maximal_graphs(11)
60
```

So, for graphs with 11 vertices, being maximal triangle-free is not equivalent to being maximal triangle-free and 3-colorable.

2 | No.2 Revision |

Your loop `for g in graphs(i):`

iterates over all graphs of size `i`

, which is abig waste of time. The `graphs()`

generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter *during* the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.

Here, the property P is "being triangle-free and having chromatic number at most 3", which is stable by edge removal.

Hence `graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3)`

will generate all graphs of size `n`

with that property, see `graphs?`

for more details.

So, here is a possible way to construct the maximal graphs you are looking for:

```
def maximal_graphs(n):
mg = []
for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
maximal=True
for e in G.complement().edges():
H = copy(G)
H.add_edge(e)
if H.is_triangle_free() and H.chromatic_number() <= 3:
maximal=False
break
if maximal:
mg.append(G)
return mg
```

You can use that function to count the graphs you ar looking for:

```
sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]
```

You can then search in the OEIS, in case something is known about such sequence:

```
sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.
sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)
```

Unfortunately, the next term differs:

```
sage: maximal_graphs(11)
60
```

So, for graphs with 11 vertices, being maximal triangle-free is not equivalent to being maximal triangle-free and 3-colorable.

You can see the following answers to get more details about generation of graphs satisfying an hereditary property:

- https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/
- https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/

3 | No.3 Revision |

Your loop `for g in graphs(i):`

iterates over all graphs of size `i`

, which is abig waste of time. The `graphs()`

generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter *during* the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.

Here, the property P is "being triangle-free and having chromatic number at most 3", which is stable by edge removal.

Hence `graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3)`

will generate all graphs of size `n`

with that property, see `graphs?`

for more details.

So, here is a possible way to construct the maximal graphs you are looking for:

```
def maximal_graphs(n):
mg = []
for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
maximal=True
for e in G.complement().edges():
H = copy(G)
H.add_edge(e)
if H.is_triangle_free() and H.chromatic_number() <= 3:
maximal=False
break
if maximal:
mg.append(G)
return mg
```

You can use that function to count the graphs you ar looking for:

```
sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]
```

You can then search in the OEIS, in case something is known about such sequence:

```
sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.
sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)
```

Unfortunately, the next term differs:

`sage: `~~maximal_graphs(11)
~~len(maximal_graphs(11))
60

So, for graphs with 11 vertices, being maximal triangle-free is not equivalent to being maximal triangle-free and 3-colorable.

You can see the following answers to get more details about generation of graphs satisfying an hereditary property:

- https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/
- https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/

4 | No.4 Revision |

Your loop `for g in graphs(i):`

iterates over all graphs of size `i`

, which is ~~abig ~~a big waste of time. The `graphs()`

generator works by adding edges, so if a property P is stable by edge removal, then it can serve as a filter *during* the generation (not after) : if some graphs does not satifsy P, then its "descendance" in the generation tree is not explored.

`graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3)`

will generate all graphs of size `n`

with that property, see `graphs?`

for more details.

So, here is a possible way to construct the maximal graphs you are looking for:

```
def maximal_graphs(n):
mg = []
for G in graphs(n, property=lambda g : g.is_triangle_free() and g.chromatic_number() <= 3):
maximal=True
for e in G.complement().edges():
H = copy(G)
H.add_edge(e)
if H.is_triangle_free() and H.chromatic_number() <= 3:
maximal=False
break
if maximal:
mg.append(G)
return mg
```

You can use that function to count the graphs you ar looking for:

```
sage: L = [len(maximal_graphs(n)) for n in range(3,11)] ; L
[1, 2, 3, 4, 6, 10, 16, 31]
```

You can then search in the OEIS, in case something is known about such sequence:

```
sage: oeis(L)
0: A216783: Number of maximal triangle-free graphs with n vertices.
sage: s = _[0]
sage: s.first_terms()
(1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687)
```

Unfortunately, the next term differs:

```
sage: len(maximal_graphs(11))
60
```

You can see the following answers to get more details about generation of graphs satisfying an hereditary property:

- https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/
- https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.