The main aim of this work is to explore a graph-theoretical characterization of Cohen-Macaulay binomial edge ideals, a class of binomial ideals defined starting from simple graphs. In fact, for a given simple finite graph \(G=(V(G), E(G))\) with \(m=|V(G)|\), we define the binomial edge ideal of \(G\) as \(J_G:=(x_iy_j - x_jy_i \mid \{i,j\} \in E(G)) \subset R=K[x_1, \ldots, x_m, y_1, \ldots, y_m].\) This definition has been presented in [J. Herzog et al., Adv. Appl. Math. 45, No. 3, 317–333 (2010; Zbl 1196.13018)] and [M. Ohtani, Commun. Algebra 39, No. 3, 905–917 (2011; Zbl 1225.13028)].
To understand the main results of this paper, we require to review some definitions. For a subset \(S \subset V(G)\), we denote by \(G\setminus S\) the subgraph induced by \(G\) on the vertices \(V(G)\setminus S\) and by \(c_G(S)\) the number of connected components of \(G \setminus S\). A subset \(S \subset V(G)\) is called a cut-point set, or simply cut set, of \(G\) if either \(S = \emptyset\) or \(c_G(S) > c_G(S \setminus \{i\})\) for every \(i\in S\). In prticular, we denote by \(\mathcal{C}(G)\) the collection of cut sets of \(G\). In addition, a graph \(G\) is called accessible if \(J_G\) is unmixed and \(\mathcal{C}(G)\) is an accessible set system, i.e., for every non-empty \(S \in \mathcal{C}(G)\) there exists \(s\in S\) such that \(S\setminus \{s\}\in \mathcal{C}(G)\). Furthermore, a block, or biconnected graph, is a graph that does not have cut vertices and adding a whisker to a vertex \(v\) of a graph means attaching a pendant edge \(\{v, f\}\), where \(f\) is a new vertex. In particular, \(f\) is a free vertex, which means that it belongs to a unique maximal clique. Historically, the study of Cohen-Macaulay binomial edge ideals concentrated on the search of classes of graphs and of constructions preserving this property. Specially, in [D. Bolognini et al., J. Algebr. Comb. 55, No. 4, 1139–1170 (2022; Zbl 1496.13036)], the authors presented the following conjecture in terms of the structure of the cut sets of the associated graph. Conjecture. Let \(G\) be a graph. Then \(R/J_G\) is Cohen-Macaulay if and only if \(G\) is accessible. This conjecture holds for chordal, bipartite, and traceable graphs. On the other hand, for every graph \(G\), the following implications hold: \begin{align*} J_G \text{ strongly unmixed } &\Rightarrow R/J_G \text{ Cohen-Macaulay }\\ & \Rightarrow R/J_G \text{ satisfies Serre's condition } (S_2) \Rightarrow G \text{ accessible}. \tag{\(\dagger\)} \end{align*} The authors of this paper tried to provide both theoretical and computational evidence for conjecture above by proving that it holds for new classes of graphs.
We finally summarize the main results of this paper in the following theorems.
Theorem. Let \(G\) be one of the following:

1.

a block with \(n\) vertices and \(k \geq n-2\) whiskers;

2.

a block with whiskers, where the vertices of the block are at most \(11\);

3.

a graph with up to \(15\) vertices.

Then the conditions in (\(\dagger\)) are all equivalent. In particular, conjecture above holds for all the graphs above and in these cases the Cohen-Macaulayness of \(R/J_G\) does not depend on the field.
Theorem. Let \(B\) be a block with \(n\) vertices and \(\overline{B}\) be the graph obtained by adding \(k > 0\) whiskers to \(B\). Assume that \(\overline{B}\) is accessible and satisfies one of the following properties:

1.

\(B\) contains a free vertex;

2.

\(B\) has a vertex of degree at most two;

3.

\(\overline{B}\) has \(k\leq 3\) whiskers;

4.

there is a cut vertex \(v\) of \(\overline{B}\) such that \(|N_B(v)| \geq \lfloor\frac{n+r}{2}\rfloor-1\), where \(r\) is the number of cut vertices adjacent to \(v\) plus one;

5.

\(\overline{B}\) has \(k = 4\) whiskers and the induced subgraph on the cut vertices of \(\overline{B}\) is a block;

6.

\(\overline{B}\) has \(k \geq n - 2\) whiskers.

Then there exists a cut vertex of \(\overline{B}\) for which \(J_{\overline{B}\setminus \{v\}}\) is unmixed.