Minimal Cohen–Macaulay independence complexes that fail to be shellable or vertex decomposable

Home  |  Research  |  Papers  |  The eight graphs  |  Census  |  Data

This page accompanies the paper Minimal examples of Cohen–Macaulay independence complexes that fail to be shellable or vertex decomposable by Adam Van Tuyl (2026) [PDF]. It collects the eight graphs found in the paper, rotating pictures of their independence complexes, and the lists of all connected graphs on n ≤ 11 vertices whose independence complexes are Cohen–Macaulay.

For any simplicial complex, vertex decomposable ⇒ shellable ⇒ Cohen–Macaulay. A search of all 1,006,700,565 connected graphs on 11 vertices shows that 11 is the smallest number of vertices where either implication fails for an independence complex Ind(G):

Contents

  1. Table of the eight graphs
  2. The graphs and their complexes: G1, G2, H1, H2, H3, H4, H5, H6
  3. Census of connected graphs, n ≤ 11
  4. Download the Cohen–Macaulay graphs
  5. How the search was done

The eight graphs

Each graph has vertex set {1, …, 11}. The entry in row v lists the neighbours w > v of vertex v, so each edge {v, w} with v < w appears exactly once. In the graph6 code, vertex i of the table is vertex i−1.

CM, not shellableShellable, not VD
vG1G2H1H2H3H4H5H6
14,5,7,84,5,8,94,6,7,94,6,7,94,6,8,94,6,8,94,6,8,94,6,9,10
25,6,8,10,115,6,8,10,115,8,9,105,8,9,105,7,9,10,115,7,9,105,7,9,10,115,7,8,9
36,7,9,106,7,9,106,7,9,10,116,7,10,116,7,10,116,7,10,116,7,10,116,7,8,11
48,9,10,117,8,117,8,10,117,8,97,8,97,8,97,8,98,9,10,11
57,9,119,10,118,10,118,10,118,9,108,9,10,118,9,107,9,10,11
68,98,9,119,119,10,1110,1110,1110,119,10,11
71010,111010,118,118,118,1110
8––11111111–11
91111––––11–
1011–––––––
|E|2525242424242425
graph6JCpdUg{[ap_JCp`eikYa|?JCQdarc]`y?JCQdarSZ`]?JCQbcvWZBM?JCQbcvWZ@]?JCQbcvWZBL?JCQbRb[f`y?

The graphs and their complexes

For each graph, the drawing on the left uses the layout from the paper, with vertices coloured by degree. The picture on the right is the independence complex Ind(G), drawn as triangles in space. All eight complexes are 2-dimensional. Drag a picture (or focus it and use the arrow keys) to rotate it; the space bar pauses the rotation. Hover over a facet in a list to highlight it. For H1–H6, the slider steps through a shelling order: the newest facet is shown in yellow.

G1  CM, not shellable

Ind(G1) is Cohen–Macaulay over a field 𝕂 if and only if char 𝕂 ≠ 2, and it is not shellable. It is a triangulation of the real projective plane ℝP2: every edge lies in exactly two triangles, every vertex link is a cycle, and the Euler characteristic is 1. Since ℝP2 cannot be embedded in ℝ3, some triangles in the picture always pass through each other. This complex is known as Terai’s example.

1234567891011
degree 4 degree 5
The graph G1 (layout as in the paper).
Ind(G1): 20 triangles on 11 vertices. Drag to rotate.

No shelling order exists for this complex.

f-vector(1, 11, 30, 20)
h-vector(1, 8, 11, 0)
graph6JCpdUg{[ap_
The 20 facets of Ind(G1)
  1. {1, 2, 3}
  2. {1, 2, 9}
  3. {1, 3, 11}
  4. {1, 6, 10}
  5. {1, 6, 11}
  6. {1, 9, 10}
  7. {2, 3, 4}
  8. {2, 4, 7}
  9. {2, 7, 9}
  10. {3, 4, 5}
  11. {3, 5, 8}
  12. {3, 8, 11}
  13. {4, 5, 6}
  14. {4, 6, 7}
  15. {5, 6, 10}
  16. {5, 8, 10}
  17. {6, 7, 11}
  18. {7, 8, 9}
  19. {7, 8, 11}
  20. {8, 9, 10}
Macaulay2 code for G1 and Ind(G1) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of G1
I = monomialIdeal(x_1*x_4, x_1*x_5, x_1*x_7, x_1*x_8, x_2*x_5, x_2*x_6, x_2*x_8, x_2*x_10, x_2*x_11, x_3*x_6, x_3*x_7, x_3*x_9, x_3*x_10, x_4*x_8, x_4*x_9, x_4*x_10, x_4*x_11, x_5*x_7, x_5*x_9, x_5*x_11, x_6*x_8, x_6*x_9, x_7*x_10, x_9*x_11, x_10*x_11);
-- Ind(G1) is the complex whose Stanley-Reisner ideal is I(G1)
D = simplicialComplex I;
-- the same complex, given by its 20 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_2*x_9, x_1*x_3*x_11, x_1*x_6*x_10, x_1*x_6*x_11, x_1*x_9*x_10, x_2*x_3*x_4, x_2*x_4*x_7, x_2*x_7*x_9, x_3*x_4*x_5, x_3*x_5*x_8, x_3*x_8*x_11, x_4*x_5*x_6, x_4*x_6*x_7, x_5*x_6*x_10, x_5*x_8*x_10, x_6*x_7*x_11, x_7*x_8*x_9, x_7*x_8*x_11, x_8*x_9*x_10};
monomialIdeal D' == I   -- true: both describe Ind(G1)

G2  CM, not shellable

Ind(G2) is Cohen–Macaulay over a field 𝕂 if and only if char 𝕂 ≠ 2, and it is not shellable. It is a triangulation of the real projective plane ℝP2: every edge lies in exactly two triangles, every vertex link is a cycle, and the Euler characteristic is 1. Since ℝP2 cannot be embedded in ℝ3, some triangles in the picture always pass through each other.

1234567891011
degree 4 degree 5 degree 6
The graph G2 (layout as in the paper).
Ind(G2): 20 triangles on 11 vertices. Drag to rotate.

No shelling order exists for this complex.

f-vector(1, 11, 30, 20)
h-vector(1, 8, 11, 0)
graph6JCp`eikYa|?
The 20 facets of Ind(G2)
  1. {1, 2, 3}
  2. {1, 2, 7}
  3. {1, 3, 11}
  4. {1, 6, 7}
  5. {1, 6, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 4, 9}
  9. {2, 7, 9}
  10. {3, 4, 5}
  11. {3, 5, 8}
  12. {3, 8, 11}
  13. {4, 5, 6}
  14. {4, 6, 10}
  15. {4, 9, 10}
  16. {5, 6, 7}
  17. {5, 7, 8}
  18. {7, 8, 9}
  19. {8, 9, 10}
  20. {8, 10, 11}
Macaulay2 code for G2 and Ind(G2) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of G2
I = monomialIdeal(x_1*x_4, x_1*x_5, x_1*x_8, x_1*x_9, x_2*x_5, x_2*x_6, x_2*x_8, x_2*x_10, x_2*x_11, x_3*x_6, x_3*x_7, x_3*x_9, x_3*x_10, x_4*x_7, x_4*x_8, x_4*x_11, x_5*x_9, x_5*x_10, x_5*x_11, x_6*x_8, x_6*x_9, x_6*x_11, x_7*x_10, x_7*x_11, x_9*x_11);
-- Ind(G2) is the complex whose Stanley-Reisner ideal is I(G2)
D = simplicialComplex I;
-- the same complex, given by its 20 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_2*x_7, x_1*x_3*x_11, x_1*x_6*x_7, x_1*x_6*x_10, x_1*x_10*x_11, x_2*x_3*x_4, x_2*x_4*x_9, x_2*x_7*x_9, x_3*x_4*x_5, x_3*x_5*x_8, x_3*x_8*x_11, x_4*x_5*x_6, x_4*x_6*x_10, x_4*x_9*x_10, x_5*x_6*x_7, x_5*x_7*x_8, x_7*x_8*x_9, x_8*x_9*x_10, x_8*x_10*x_11};
monomialIdeal D' == I   -- true: both describe Ind(G2)

H1  shellable, not VD

Ind(H1) is shellable (so Cohen–Macaulay over every field) but not vertex decomposable. It is not a surface: some edges lie in three triangles.

1234567891011
degree 4 degree 5
The graph H1 (layout as in the paper).
Ind(H1): 21 triangles on 11 vertices. Drag to rotate.
Shelling order (the shelling order given in the paper)
  1. {9, 10, 11}
  2. {1, 10, 11}
  3. {7, 9, 11}
  4. {2, 7, 11}
  5. {1, 2, 11}
  6. {8, 9, 10}
  7. {6, 8, 10}
  8. {1, 8, 10}
  9. {7, 8, 9}
  10. {5, 7, 9}
  11. {4, 5, 9}
  12. {6, 7, 8}
  13. {1, 3, 8}
  14. {5, 6, 7}
  15. {2, 6, 7}
  16. {4, 5, 6}
  17. {2, 4, 6}
  18. {1, 2, 3}
  19. {2, 3, 4}
  20. {3, 4, 5}
  21. {1, 3, 5}
f-vector(1, 11, 31, 21)
h-vector(1, 8, 12, 0)
graph6JCQdarc]`y?
The 21 facets of Ind(H1)
  1. {1, 2, 3}
  2. {1, 2, 11}
  3. {1, 3, 5}
  4. {1, 3, 8}
  5. {1, 8, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 4, 6}
  9. {2, 6, 7}
  10. {2, 7, 11}
  11. {3, 4, 5}
  12. {4, 5, 6}
  13. {4, 5, 9}
  14. {5, 6, 7}
  15. {5, 7, 9}
  16. {6, 7, 8}
  17. {6, 8, 10}
  18. {7, 8, 9}
  19. {7, 9, 11}
  20. {8, 9, 10}
  21. {9, 10, 11}
Macaulay2 code for H1 and Ind(H1) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of H1
I = monomialIdeal(x_1*x_4, x_1*x_6, x_1*x_7, x_1*x_9, x_2*x_5, x_2*x_8, x_2*x_9, x_2*x_10, x_3*x_6, x_3*x_7, x_3*x_9, x_3*x_10, x_3*x_11, x_4*x_7, x_4*x_8, x_4*x_10, x_4*x_11, x_5*x_8, x_5*x_10, x_5*x_11, x_6*x_9, x_6*x_11, x_7*x_10, x_8*x_11);
-- Ind(H1) is the complex whose Stanley-Reisner ideal is I(H1)
D = simplicialComplex I;
-- the same complex, given by its 21 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_2*x_11, x_1*x_3*x_5, x_1*x_3*x_8, x_1*x_8*x_10, x_1*x_10*x_11, x_2*x_3*x_4, x_2*x_4*x_6, x_2*x_6*x_7, x_2*x_7*x_11, x_3*x_4*x_5, x_4*x_5*x_6, x_4*x_5*x_9, x_5*x_6*x_7, x_5*x_7*x_9, x_6*x_7*x_8, x_6*x_8*x_10, x_7*x_8*x_9, x_7*x_9*x_11, x_8*x_9*x_10, x_9*x_10*x_11};
monomialIdeal D' == I   -- true: both describe Ind(H1)

H2  shellable, not VD

Ind(H2) is shellable (so Cohen–Macaulay over every field) but not vertex decomposable. It is not a surface: some edges lie in three triangles.

1234567891011
degree 4 degree 5
The graph H2 (layout as in the paper).
Ind(H2): 21 triangles on 11 vertices. Drag to rotate.
Shelling order (a shelling order found by our code)
  1. {1, 2, 3}
  2. {1, 2, 11}
  3. {1, 3, 5}
  4. {1, 3, 8}
  5. {1, 8, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 4, 6}
  9. {2, 4, 11}
  10. {2, 6, 7}
  11. {3, 4, 5}
  12. {3, 5, 9}
  13. {3, 8, 9}
  14. {4, 5, 6}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {5, 7, 9}
  18. {7, 8, 9}
  19. {6, 7, 8}
  20. {8, 9, 10}
  21. {9, 10, 11}
f-vector(1, 11, 31, 21)
h-vector(1, 8, 12, 0)
graph6JCQdarSZ`]?
The 21 facets of Ind(H2)
  1. {1, 2, 3}
  2. {1, 2, 11}
  3. {1, 3, 5}
  4. {1, 3, 8}
  5. {1, 8, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 4, 6}
  9. {2, 4, 11}
  10. {2, 6, 7}
  11. {3, 4, 5}
  12. {3, 5, 9}
  13. {3, 8, 9}
  14. {4, 5, 6}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {5, 7, 9}
  18. {6, 7, 8}
  19. {7, 8, 9}
  20. {8, 9, 10}
  21. {9, 10, 11}
Macaulay2 code for H2 and Ind(H2) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of H2
I = monomialIdeal(x_1*x_4, x_1*x_6, x_1*x_7, x_1*x_9, x_2*x_5, x_2*x_8, x_2*x_9, x_2*x_10, x_3*x_6, x_3*x_7, x_3*x_10, x_3*x_11, x_4*x_7, x_4*x_8, x_4*x_9, x_5*x_8, x_5*x_10, x_5*x_11, x_6*x_9, x_6*x_10, x_6*x_11, x_7*x_10, x_7*x_11, x_8*x_11);
-- Ind(H2) is the complex whose Stanley-Reisner ideal is I(H2)
D = simplicialComplex I;
-- the same complex, given by its 21 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_2*x_11, x_1*x_3*x_5, x_1*x_3*x_8, x_1*x_8*x_10, x_1*x_10*x_11, x_2*x_3*x_4, x_2*x_4*x_6, x_2*x_4*x_11, x_2*x_6*x_7, x_3*x_4*x_5, x_3*x_5*x_9, x_3*x_8*x_9, x_4*x_5*x_6, x_4*x_10*x_11, x_5*x_6*x_7, x_5*x_7*x_9, x_6*x_7*x_8, x_7*x_8*x_9, x_8*x_9*x_10, x_9*x_10*x_11};
monomialIdeal D' == I   -- true: both describe Ind(H2)

H3  shellable, not VD

Ind(H3) is shellable (so Cohen–Macaulay over every field) but not vertex decomposable. It is not a surface: some edges lie in three triangles.

1234567891011
degree 4 degree 5
The graph H3 (layout as in the paper).
Ind(H3): 21 triangles on 11 vertices. Drag to rotate.
Shelling order (a shelling order found by our code)
  1. {1, 2, 3}
  2. {1, 3, 5}
  3. {1, 5, 7}
  4. {1, 5, 11}
  5. {1, 7, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 3, 8}
  9. {2, 4, 6}
  10. {2, 6, 8}
  11. {3, 4, 5}
  12. {3, 8, 9}
  13. {4, 5, 6}
  14. {4, 5, 11}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {6, 8, 9}
  18. {6, 7, 9}
  19. {7, 9, 10}
  20. {8, 9, 10}
  21. {9, 10, 11}
f-vector(1, 11, 31, 21)
h-vector(1, 8, 12, 0)
graph6JCQbcvWZBM?
The 21 facets of Ind(H3)
  1. {1, 2, 3}
  2. {1, 3, 5}
  3. {1, 5, 7}
  4. {1, 5, 11}
  5. {1, 7, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 3, 8}
  9. {2, 4, 6}
  10. {2, 6, 8}
  11. {3, 4, 5}
  12. {3, 8, 9}
  13. {4, 5, 6}
  14. {4, 5, 11}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {6, 7, 9}
  18. {6, 8, 9}
  19. {7, 9, 10}
  20. {8, 9, 10}
  21. {9, 10, 11}
Macaulay2 code for H3 and Ind(H3) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of H3
I = monomialIdeal(x_1*x_4, x_1*x_6, x_1*x_8, x_1*x_9, x_2*x_5, x_2*x_7, x_2*x_9, x_2*x_10, x_2*x_11, x_3*x_6, x_3*x_7, x_3*x_10, x_3*x_11, x_4*x_7, x_4*x_8, x_4*x_9, x_5*x_8, x_5*x_9, x_5*x_10, x_6*x_10, x_6*x_11, x_7*x_8, x_7*x_11, x_8*x_11);
-- Ind(H3) is the complex whose Stanley-Reisner ideal is I(H3)
D = simplicialComplex I;
-- the same complex, given by its 21 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_3*x_5, x_1*x_5*x_7, x_1*x_5*x_11, x_1*x_7*x_10, x_1*x_10*x_11, x_2*x_3*x_4, x_2*x_3*x_8, x_2*x_4*x_6, x_2*x_6*x_8, x_3*x_4*x_5, x_3*x_8*x_9, x_4*x_5*x_6, x_4*x_5*x_11, x_4*x_10*x_11, x_5*x_6*x_7, x_6*x_7*x_9, x_6*x_8*x_9, x_7*x_9*x_10, x_8*x_9*x_10, x_9*x_10*x_11};
monomialIdeal D' == I   -- true: both describe Ind(H3)

H4  shellable, not VD

Ind(H4) is shellable (so Cohen–Macaulay over every field) but not vertex decomposable. It is not a surface: some edges lie in three triangles.

1234567891011
degree 4 degree 5
The graph H4 (layout as in the paper).
Ind(H4): 21 triangles on 11 vertices. Drag to rotate.
Shelling order (a shelling order found by our code)
  1. {1, 2, 3}
  2. {1, 2, 11}
  3. {1, 3, 5}
  4. {1, 5, 7}
  5. {1, 7, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 3, 8}
  9. {2, 4, 6}
  10. {2, 4, 11}
  11. {2, 6, 8}
  12. {3, 4, 5}
  13. {3, 8, 9}
  14. {4, 5, 6}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {6, 8, 9}
  18. {6, 7, 9}
  19. {7, 9, 10}
  20. {8, 9, 10}
  21. {9, 10, 11}
f-vector(1, 11, 31, 21)
h-vector(1, 8, 12, 0)
graph6JCQbcvWZ@]?
The 21 facets of Ind(H4)
  1. {1, 2, 3}
  2. {1, 2, 11}
  3. {1, 3, 5}
  4. {1, 5, 7}
  5. {1, 7, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 3, 8}
  9. {2, 4, 6}
  10. {2, 4, 11}
  11. {2, 6, 8}
  12. {3, 4, 5}
  13. {3, 8, 9}
  14. {4, 5, 6}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {6, 7, 9}
  18. {6, 8, 9}
  19. {7, 9, 10}
  20. {8, 9, 10}
  21. {9, 10, 11}
Macaulay2 code for H4 and Ind(H4) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of H4
I = monomialIdeal(x_1*x_4, x_1*x_6, x_1*x_8, x_1*x_9, x_2*x_5, x_2*x_7, x_2*x_9, x_2*x_10, x_3*x_6, x_3*x_7, x_3*x_10, x_3*x_11, x_4*x_7, x_4*x_8, x_4*x_9, x_5*x_8, x_5*x_9, x_5*x_10, x_5*x_11, x_6*x_10, x_6*x_11, x_7*x_8, x_7*x_11, x_8*x_11);
-- Ind(H4) is the complex whose Stanley-Reisner ideal is I(H4)
D = simplicialComplex I;
-- the same complex, given by its 21 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_2*x_11, x_1*x_3*x_5, x_1*x_5*x_7, x_1*x_7*x_10, x_1*x_10*x_11, x_2*x_3*x_4, x_2*x_3*x_8, x_2*x_4*x_6, x_2*x_4*x_11, x_2*x_6*x_8, x_3*x_4*x_5, x_3*x_8*x_9, x_4*x_5*x_6, x_4*x_10*x_11, x_5*x_6*x_7, x_6*x_7*x_9, x_6*x_8*x_9, x_7*x_9*x_10, x_8*x_9*x_10, x_9*x_10*x_11};
monomialIdeal D' == I   -- true: both describe Ind(H4)

H5  shellable, not VD

Ind(H5) is shellable (so Cohen–Macaulay over every field) but not vertex decomposable. It is not a surface: some edges lie in three triangles.

1234567891011
degree 4 degree 5
The graph H5 (layout as in the paper).
Ind(H5): 21 triangles on 11 vertices. Drag to rotate.
Shelling order (a shelling order found by our code)
  1. {1, 2, 3}
  2. {1, 3, 5}
  3. {1, 5, 7}
  4. {1, 5, 11}
  5. {1, 7, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 3, 8}
  9. {2, 4, 6}
  10. {2, 6, 8}
  11. {3, 4, 5}
  12. {3, 8, 9}
  13. {4, 5, 6}
  14. {4, 5, 11}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {6, 8, 9}
  18. {6, 7, 9}
  19. {7, 9, 10}
  20. {8, 9, 10}
  21. {8, 10, 11}
f-vector(1, 11, 31, 21)
h-vector(1, 8, 12, 0)
graph6JCQbcvWZBL?
The 21 facets of Ind(H5)
  1. {1, 2, 3}
  2. {1, 3, 5}
  3. {1, 5, 7}
  4. {1, 5, 11}
  5. {1, 7, 10}
  6. {1, 10, 11}
  7. {2, 3, 4}
  8. {2, 3, 8}
  9. {2, 4, 6}
  10. {2, 6, 8}
  11. {3, 4, 5}
  12. {3, 8, 9}
  13. {4, 5, 6}
  14. {4, 5, 11}
  15. {4, 10, 11}
  16. {5, 6, 7}
  17. {6, 7, 9}
  18. {6, 8, 9}
  19. {7, 9, 10}
  20. {8, 9, 10}
  21. {8, 10, 11}
Macaulay2 code for H5 and Ind(H5) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of H5
I = monomialIdeal(x_1*x_4, x_1*x_6, x_1*x_8, x_1*x_9, x_2*x_5, x_2*x_7, x_2*x_9, x_2*x_10, x_2*x_11, x_3*x_6, x_3*x_7, x_3*x_10, x_3*x_11, x_4*x_7, x_4*x_8, x_4*x_9, x_5*x_8, x_5*x_9, x_5*x_10, x_6*x_10, x_6*x_11, x_7*x_8, x_7*x_11, x_9*x_11);
-- Ind(H5) is the complex whose Stanley-Reisner ideal is I(H5)
D = simplicialComplex I;
-- the same complex, given by its 21 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_3*x_5, x_1*x_5*x_7, x_1*x_5*x_11, x_1*x_7*x_10, x_1*x_10*x_11, x_2*x_3*x_4, x_2*x_3*x_8, x_2*x_4*x_6, x_2*x_6*x_8, x_3*x_4*x_5, x_3*x_8*x_9, x_4*x_5*x_6, x_4*x_5*x_11, x_4*x_10*x_11, x_5*x_6*x_7, x_6*x_7*x_9, x_6*x_8*x_9, x_7*x_9*x_10, x_8*x_9*x_10, x_8*x_10*x_11};
monomialIdeal D' == I   -- true: both describe Ind(H5)

H6  shellable, not VD

Ind(H6) is shellable (so Cohen–Macaulay over every field) but not vertex decomposable. It is not a surface: some edges lie in three triangles.

1234567891011
degree 4 degree 5
The graph H6 (layout as in the paper).
Ind(H6): 20 triangles on 11 vertices. Drag to rotate.
Shelling order (a shelling order found by our code)
  1. {1, 2, 3}
  2. {1, 2, 11}
  3. {1, 3, 5}
  4. {1, 5, 8}
  5. {1, 7, 8}
  6. {1, 7, 11}
  7. {2, 3, 4}
  8. {2, 3, 10}
  9. {2, 4, 6}
  10. {2, 10, 11}
  11. {3, 4, 5}
  12. {3, 9, 10}
  13. {4, 5, 6}
  14. {5, 6, 8}
  15. {6, 7, 8}
  16. {4, 6, 7}
  17. {9, 10, 11}
  18. {7, 9, 11}
  19. {7, 8, 9}
  20. {8, 9, 10}
f-vector(1, 11, 30, 20)
h-vector(1, 8, 11, 0)
graph6JCQbRb[f`y?
The 20 facets of Ind(H6)
  1. {1, 2, 3}
  2. {1, 2, 11}
  3. {1, 3, 5}
  4. {1, 5, 8}
  5. {1, 7, 8}
  6. {1, 7, 11}
  7. {2, 3, 4}
  8. {2, 3, 10}
  9. {2, 4, 6}
  10. {2, 10, 11}
  11. {3, 4, 5}
  12. {3, 9, 10}
  13. {4, 5, 6}
  14. {4, 6, 7}
  15. {5, 6, 8}
  16. {6, 7, 8}
  17. {7, 8, 9}
  18. {7, 9, 11}
  19. {8, 9, 10}
  20. {9, 10, 11}
Macaulay2 code for H6 and Ind(H6) 
needsPackage "SimplicialComplexes";
R = QQ[x_1..x_11];
-- edge ideal of H6
I = monomialIdeal(x_1*x_4, x_1*x_6, x_1*x_9, x_1*x_10, x_2*x_5, x_2*x_7, x_2*x_8, x_2*x_9, x_3*x_6, x_3*x_7, x_3*x_8, x_3*x_11, x_4*x_8, x_4*x_9, x_4*x_10, x_4*x_11, x_5*x_7, x_5*x_9, x_5*x_10, x_5*x_11, x_6*x_9, x_6*x_10, x_6*x_11, x_7*x_10, x_8*x_11);
-- Ind(H6) is the complex whose Stanley-Reisner ideal is I(H6)
D = simplicialComplex I;
-- the same complex, given by its 20 facets
D' = simplicialComplex {x_1*x_2*x_3, x_1*x_2*x_11, x_1*x_3*x_5, x_1*x_5*x_8, x_1*x_7*x_8, x_1*x_7*x_11, x_2*x_3*x_4, x_2*x_3*x_10, x_2*x_4*x_6, x_2*x_10*x_11, x_3*x_4*x_5, x_3*x_9*x_10, x_4*x_5*x_6, x_4*x_6*x_7, x_5*x_6*x_8, x_6*x_7*x_8, x_7*x_8*x_9, x_7*x_9*x_11, x_8*x_9*x_10, x_9*x_10*x_11};
monomialIdeal D' == I   -- true: both describe Ind(H6)

Census of connected graphs on n ≤ 11 vertices

The number of connected graphs G on n vertices that are well-covered (that is, Ind(G) is pure), and for which Ind(G) is Cohen–Macaulay over ℚ, shellable, and vertex decomposable. The rows for n ≤ 10 were computed by Baker, Vander Meulen and Van Tuyl (Discrete Math. 341 (2018)); the row for n = 11 is new. The first two columns are OEIS A001349 and A222625.

nConnected
graphs		Well-
covered		Cohen–Macaulay
(over ℚ)		ShellableVertex
decomposable
111111
211111
321111
463222
5216555
611227202020
7853108828282
811,117788565565565
9261,0809,0355,6885,6885,688
1011,716,571196,928102,039102,039102,039
111,006,700,5657,797,8773,247,4903,247,4883,247,482

Download the Cohen–Macaulay graphs

Each file lists every connected graph on n vertices whose independence complex is Cohen–Macaulay over ℚ, one graph per line in graph6 format, sorted. For n = 11 the file contains 3,247,490 graphs; 8 of them are the graphs above, and the rest are vertex decomposable.

nCM graphsPlain textgzip
21cm_n2.txt (3 B)cm_n2.txt.gz
31cm_n3.txt (3 B)cm_n3.txt.gz
42cm_n4.txt (6 B)cm_n4.txt.gz
55cm_n5.txt (20 B)cm_n5.txt.gz
620cm_n6.txt (100 B)cm_n6.txt.gz
782cm_n7.txt (492 B)cm_n7.txt.gz
8565cm_n8.txt (3,955 B)cm_n8.txt.gz
95,688cm_n9.txt (45.5 kB)cm_n9.txt.gz
10102,039cm_n10.txt (1.0 MB)cm_n10.txt.gz
113,247,490cm_n11.txt (39.0 MB)cm_n11.txt.gz

To read a file in Macaulay2 (graph6 vertex i becomes the variable xi+1):

needsPackage "Nauty";
R = QQ[x_1..x_11];
L = lines get "cm_n11.txt";                   -- one graph6 string per line
I = stringToEdgeIdeal(first L, R);            -- edge ideal of the first graph
G = stringToGraph(first L, R);                -- the same graph as a Graph

How the search was done

The census was carried out twice, independently. The first run (2022–23) used Macaulay2 with the packages EdgeIdeals, Nauty and SimplicialDecomposability. The second run (2026) used separate code written in Python, with the graphs generated by nauty. In both runs, Cohen–Macaulayness was tested over ℚ. The second run also counted the well-covered graphs, matching OEIS A222625, and reproduced the table above for n ≤ 10. Both runs found the same eight graphs. Full details are in the paper.

Last Updated: October 4, 2026  |  URL: https://math.mcmaster.ca/~vantuyl/research/minimal-cm/