BINOMIAL EDGE IDEALS OF BIPARTITE GRAPHS

arXiv:1704.00152v2 [] 6 May 2017

DAVIDE BOLOGNINI, ANTONIO MACCHIA, FRANCESCO STRAZZANTI
Abstract. We classify the bipartite graphs G whose binomial edge ideal JG is Cohen-Macaulay. The
connected components of such graphs can be obtained by gluing a finite number of basic blocks with
two operations. In this context we prove the converse of a well-known result due to Hartshorne, showing
that the Cohen-Macaulayness of these ideals is equivalent to the connectedness of their dual graphs. We
study interesting properties also for non-bipartite graphs and in the unmixed case, constructing classes of
bipartite graphs with JG unmixed and not Cohen-Macaulay.

1. Introduction
Binomial edge ideals were introduced independently in [10] and [17]. They are a natural generalization
of the ideals of 2-minors of a (2 × n)-generic matrix [3]: their generators are those 2-minors whose column
indices correspond to the edges of a graph. In this perspective, the ideals of 2-minors are binomial edge
ideals of complete graphs. On the other hand, binomial edge ideals arise naturally in Algebraic Statistics,
in the context of conditional independence ideals, see [10, Section 4].
More precisely, given a finite simple graph G on the vertex set [n] = {1, . . . , n}, the binomial edge ideal
associated with G is the ideal
JG = (xi yj − xj yi : {i, j} is an edge of G) ⊂ R = K[xi , yi : i ∈ [n]].
Binomial edge ideals have been extensively studied, see e.g. [1], [5], [6], [13], [14], [15], [18], [19]. Yet
a number of interesting questions is still unanswered. In particular, many authors have studied classes of
Cohen-Macaulay binomial edge ideals in terms of the associated graph, see e.g. [1], [5], [13], [18], [19].
Some of these results concern a class of chordal graphs, the so-called closed graphs, introduced in [10], and
their generalizations, such as block and generalized block graphs [13].
In the context of squarefree monomial ideals, any graph can be associated with the so-called edge ideal,
whose generators are monomials of degree 2 corresponding to the edges of the graph. Herzog and Hibi, in
[9, Theorem 3.4], classified Cohen-Macaulay edge ideals of bipartite graphs in purely combinatorial terms.
In the same spirit, we provide a combinatorial classification of Cohen-Macaulay binomial edge ideals of
bipartite graphs. In particular, we present a family of bipartite graphs Fm whose binomial edge ideal
is Cohen-Macaulay, and we prove that, if G is connected and bipartite, then JG is Cohen-Macaulay if
and only if G can be obtained recursively by gluing a finite number of graphs of the form Fm via two
operations.
2010 Mathematics Subject Classification. Primary 13H10, 13C05, 05C40; Secondary 05E40, 05C99.
Key words and phrases. Binomial edge ideals, bipartite graphs, Cohen-Macaulay rings, unmixed ideals, dual graph of an
ideal.
The first and the second author were supported by INdAM.
The third author was partially supported by MTM2013-46231-P (Ministerio de Economıía y Competitividad) and FEDER.
1

2

We now explain in more detail the basic blocks and the operations in our classification. For the
terminology about graphs we refer to [4].
Basic blocks: For every m ≥ 1, let Fm be the graph (see Figure 1) on the vertex set [2m] and with
edge set
E(Fm ) = {{2i, 2j − 1} : i = 1, . . . , m, j = i, . . . , m} .
Notice that F1 is the single edge {1, 2} and F2 is the path of length 3.
1

3

5

1

3

5

7

2

4

6

2

4

6

8

(a) The graph F3

(b) The graph F4

Figure 1
Operation ∗: For i = 1, 2, let Gi be a graph with at least one vertex fi of degree one, i.e., a leaf of
Gi . We denote the graph G obtained by identifying f1 and f2 by G = (G1 , f1 ) ∗ (G2 , f2 ), see Figure 2(a).
This is a particular case of an operation studied by Rauf and Rinaldo in [18, Section 2].
Operation ◦: For i = 1, 2, let Gi be a graph with at least one leaf fi , vi its neighbour and assume
degGi (vi ) ≥ 3. We define G = (G1 , f1 ) ◦ (G2 , f2 ) to be the graph obtained from G1 and G2 by removing
the leaves f1 , f2 and identifying v1 and v2 , see Figure 2(b).
For both operations, if it is not important to specify the vertices fi or it is clear from the context, we
simply write G1 ∗ G2 or G1 ◦ G2 .

v1 = v2

f1 = f2

(b) The graph F3 ◦ F4

(a) The graph F3 ∗ F4

Figure 2
Finally, we recall the notion of dual graph of an ideal, which is one of the main tools in the proof of our
classification. We follow the notation used in [2].
Dual graph: Let I be an ideal in a polynomial ring A = K[x1 , . . . , xn ] and let p1 , . . . , pr be the minimal
prime ideals of I. The dual graph D(I) is a graph with vertex set [r] and edge set
{{i, j} : ht(pi + pj ) − 1 = ht(pi ) = ht(pj ) = ht(I)}.
This notion was originally studied by Hartshorne in [8] in terms of connectedness in codimension one.
By [8, Corollary 2.4], if A/I is Cohen-Macaulay, then the algebraic variety defined by I is connected in
codimension one, hence I is unmixed by [8, Remark 2.4.1]. The connectedness of the dual graph translates

3

in combinatorial terms the notion of connectedness in codimension one, see [8, Proposition 1.1]. Thus, if
A/I is Cohen-Macaulay, then D(I) is connected. The converse does not hold in general, see for instance
Remark 5.1. We will show that for binomial edge ideals of connected bipartite graphs this is indeed an
equivalence. In geometric terms, this means that the algebraic variety defined by JG is Cohen-Macaulay
if and only if it is connected in codimension one.
Given a graph G, the ideal JG is Cohen-Macaulay if and only if the binomial edge ideal of each connected
component of G is Cohen–Macaulay. Thus, we may assume G connected with at least two vertices.
Before stating the main result, we recall the notion of cut set, which is central in the study of binomial
edge ideals. In fact, there is a bijection between the cut sets of a graph G and the minimal prime ideals
of JG , see [10, Section 3]. For a subset S ⊆ [n], let cG (S) be the number of connected components of the
induced subgraph G[n]\S . The set S is called cut set of G if S = ∅ or S 6= ∅ and cG (S \ {i}) < cG (S) for
every i ∈ S. Moreover, we call cut vertex a cut set of cardinality one. We denote by M(G) the set of cut
sets of G.
We are now ready to state our main result.
Theorem 6.1. Let G be a connected bipartite graph. The following properties are equivalent:
a)
b)
c)
d)

JG is Cohen-Macaulay;
the dual graph D(JG ) is connected;
G = A1 ∗ A2 ∗ · · · ∗ Ak , where Ai = Fm or Ai = Fm1 ◦ · · · ◦ Fmr , for some m ≥ 1 and mj ≥ 3;
JG is unmixed and for every non-empty S ∈ M(G), there exists s ∈ S such that S \ {s} ∈ M(G).

The paper is structured as follows. In Section 2 we study unmixed binomial edge ideals of bipartite
graphs. A combinatorial characterization of unmixedness was already proved in [10] (see also [18, Lemma
2.5]), in terms of the cut sets of the underlying graph.
A first distinguishing fact about bipartite graphs with JG unmixed is that they have exactly two leaves
(Proposition 2.3). This, in particular, means that G has at least two cut vertices. In Proposition 2.8,
we present a construction that is useful in the study of the basic blocks and to produce new examples of
unmixed binomial edge ideals, which are not Cohen-Macaulay.
In Section 3 we prove that the ideals JFm , associated with the basic blocks of our construction, are
Cohen-Macaulay, see Proposition 3.3. In Section 4 we study the operations ∗ and ◦. In [18, Theorem 2.7],
Rauf and Rinaldo proved that JG1 ∗G2 is Cohen-Macaulay if and only if so are JG1 and JG2 . In Theorem
4.9, we show that JG is Cohen-Macaulay if G = Fm1 ◦ · · · ◦ Fmk , for every k ≥ 2 and mi ≥ 3. Using these
results, we prove the implication c) ⇒ a) of Theorem 6.1.
Section 5 is devoted to the study of the dual graph of binomial edge ideals. This is one of the main tools
in the proof of Theorem 6.1. First of all, given a (not necessarily bipartite) graph G with JG unmixed, in
Theorem 5.2 we provide an explicit description of the edges of the dual graph D(JG ) in terms of the cut
sets of G. This allows us to show infinite families of bipartite graphs whose binomial edge ideal is unmixed
and not Cohen-Macaulay, see Examples 2.2 and 5.4.
A crucial result concerns a basic, yet elusive, property of cut sets of unmixed binomial edge ideals. In
Lemma 5.5, we show that, mostly for bipartite graphs and under some assumption, the intersection of any
two cut sets is a cut set. This leads to the proof of the equivalence b) ⇔ d) in Theorem 6.1, see Theorem
5.7. On the other hand, if G = G1 ∗ G2 or G = G1 ◦ G2 is bipartite and D(JG ) is connected, then the dual

4

graphs of G1 and G2 are connected, see Theorem 5.8. Thus, we may reduce to consider bipartite graphs
with exactly two cut vertices and prove the implication b) ⇒ c) of Theorem 6.1.
It is worth noting that, the main theorem gives also a classification of other classes of Cohen-Macaulay
binomial ideals associated with bipartite graphs, Corollary 6.2: Lovász-Saks-Schrijver ideals [11], permanental edge ideals [11, Section 3] and parity binomial edge ideals [12].
As an application of the main result, in Corollary 6.3, we show that Cohen-Macaulay binomial edge
ideals of bipartite graphs are Hirsch, meaning that the diameter of the dual graph of JG is bounded above
by the height of JG , verifying [2, Conjecture 1.6].
All the results presented in this paper are independent of the field.
2. Unmixed binomial edge ideals of bipartite graphs
In this paper all graphs are finite and simple (without loops and multiple edges). In what follows,
unless otherwise stated, we assume that G is a connected graph with at least two vertices. Given a graph
G, we denote by V (G) its vertex set and by E(G) its edge set. If G is a bipartite graph, we denote by
V (G) = V1 ⊔ V2 the bipartition of the vertex set and call V1 , V2 the bipartition sets of G.
For a subset S ⊆ V (G), we denote by GS the subgraph induced in G by S, which is the graph with
vertex set S and edge set consisting of all the edges of G with both endpoints in S.
We recall some definitions and results from [10]. Let G be a graph with vertex set [n]. We denote
by R = K[xi , yi : i ∈ [n]] the polynomial ring in which the ideal JG is defined and, if S ⊆ [n], we set
S = [n] \ S. Let cG (S), or simply c(S), be the number of connected components of the induced subgraph
ei the complete
GS and let G1 , . . . , GcG (S) be the connected components of GS . For each Gi , denote by G
graph on V (Gi ) and define the ideal
!
[
{xi , yi }, JGe1 , . . . , JGe
PS (G) =
.
i∈S

cG (S)

In [10, Section 3], it is shown that PS (G) is a prime ideal for every S ⊆ [n], ht(PS (G)) = n + |S| − cG (S)
T
and JG = S⊆[n] PS (G). Moreover, PS (G) is a minimal prime ideal of JG if and only if S = ∅ or S 6= ∅
and cG (S \ {i}) < cG (S) for every i ∈ S. In simple terms the last condition means that, adding a vertex
of S to GS , we connect at least two connected components of GS . We set
M(G) = {S ⊂ [n] : PS (G) is a minimal prime ideal of JG }
= {∅} ∪ {S ⊂ [n] : S 6= ∅, cG (S \ {i}) < cG (S) for every i ∈ S},
and we call cut sets of G the elements of M(G). If {v} ∈ M(G), we say that v is a cut vertex of G.
We further recall that a clique of a graph G is a subset C ⊆ V (G) such that GC is complete. A free
vertex of G is a vertex that belongs to exactly one maximal clique of G. A vertex of degree 1 in G, which
in particular is a free vertex, is called a leaf of G.

Remark 2.1. If v is a free vertex of a graph G, then v ∈
/ S, for every S ∈ M(G). In fact, if v ∈ S, for
some S ∈ M(G), then cG (S) = cG (S \ {v}).
Recall that an ideal is unmixed if all its minimal primes have the same height. By [18, Lemma 2.5], JG
is unmixed if and only if for every S ∈ M(G),
(1)

cG (S) = |S| + 1.

5

This follows from the equality ht(P∅ (G)) = n − 1 = ht(PS (G)) = n + |S| − cG (S).
Moreover, for every graph G, with JG unmixed, we have that dim(R/JG ) = |V (G)| + c, where c is the
number of connected components of G, see [10, Corollary 3.3].
In this section, we study some properties of unmixed binomial edge ideals of bipartite graphs. It is
well-known that if JG is Cohen-Macaulay, then JG is unmixed. The converse is, in general, not true,
also for binomial edge ideals of bipartite graphs. In fact, in the following example we show two classes of
bipartite graphs whose binomial edge ideals are unmixed but not Cohen-Macaulay.
Example 2.2. For every k ≥ 4, let Mk,k be the graph with vertex set [2k] and edge set
E(Mk,k ) = {{1, 2}, {2k − 1, 2k}} ∪ {{2i, 2j − 1} : i = 1, . . . , k − 1, j = 2, . . . , k},
see Figure 3(a), and let Mk−1,k be the graph with vertex set [2k − 1] and edge set
E(Mk−1,k ) = {{1, 2}, {2k − 2, 2k − 1}} ∪ {{2i, 2j − 1} : i = 1, . . . , k − 1, j = 2, . . . , k − 1},
see Figure 3(b).
1

3

5

7

2

4

6

8

1

3

2

(a) The graph M4,4

5

4

7

6

(b) The graph M3,4

Figure 3
Notice that the graphs Mk,k and Mk−1,k are obtained by adding two whiskers to some complete bipartite
graph. Recall that adding a whisker to a graph G means adding a new vertex and connect it to one of the
vertices of G.
Let V1 ⊔ V2 be the bipartition of Mk,k and of Mk−1,k such that V1 contains the odd labelled vertices
and V2 contains the even labelled vertices. We claim that
M(Mk,k ) = {∅, {2}, {2k − 1}, {2, 2k − 1}, V1 \ {1}, V2 \ {2k}} and
M(Mk−1,k ) = {∅, {2}, {2k − 2}, {2, 2k − 2}, V1 \ {1, 2k − 1}, V2 }.
The inclusion ⊇ is clear. We prove the other inclusion for Mk,k , the proof is similar for Mk−1,k . Let
S ∈ M(Mk,k ). If S ⊆ {2, 2k − 1}, there is nothing to prove. If there exists v ∈ S \ {2, 2k − 1}, then
S = V1 \ {1} or S = V2 \ {2k}. In fact, if v ∈ V1 \ {1} and there is w ∈ (V1 \ {1}) \ S, then c(S \ {v}) = c(S),
a contradiction. Hence, V1 \ {1} ⊆ S. On the other hand, if w ∈ V2 \ {2k}, then w ∈
/ S. This shows that
S = V1 \ {1} The other case is similar.
Moreover, it is easy to check that JMk,k and JMk−1,k are unmixed. In Example 5.4 we will show that
these ideals are not Cohen-Macaulay.
A first nice fact about bipartite graphs with unmixed binomial edge ideal is that they have at least two
cut vertices.
Proposition 2.3. Let G be a bipartite graph such that JG is unmixed. Then G has exactly 2 leaves.

6

Proof. Let V (G) = V1 ⊔ V2 be the bipartition of G, with m1 = |V1 | ≥ 1 and m2 = |V2 | ≥ 1. Assume that G
has exactly h leaves, f1 , . . . , fh , in V1 and k leaves, g1 , . . . , gk , in V2 . We claim that S1 = V1 \ {f1 , . . . , fh }
and S2 = V2 \ {g1 , . . . , gk } are cut sets of G. Notice that cG (S1 ) = |V2 | = m2 and cG (S1 \ {v}) < cG (S1 )
since the vertex v joins at least two connected components of GS 1 . By symmetry, the claim is true for
S2 and, in particular cG (S2 ) = |V1 | = m1 . From the unmixedness of JG it follows that ht(P∅ (G)) =
ht(PS1 (G)) and ht(P∅ (G)) = ht(PS2 (G)). Thus n − 1 = n + |S1 | − cG (S1 ) = n + m1 − h − m2 and
n − 1 = n + |S2 | − cG (S2 ) = n + m2 − k − m1 . Hence h = m1 − m2 + 1 and k = m2 − m1 + 1. The sum of
the two equations yields h + k = 2.

Remark 2.4. Assume that G is bipartite and JG is unmixed. The proof of Proposition 2.3 implies that:
(i) either h = 2 and k = 0, i.e., the two leaves are in the same bipartition set and in this case
m1 = m2 + 1, or h = 1 and k = 1, i.e., each bipartition set contains exactly one leaf and in this
case m1 = m2 ;
(ii) if G has at least 4 vertices, then the leaves cannot be attached to the same vertex v, otherwise
cG ({v}) ≥ 3 > 2 = |{v}| + 1, against the unmixedness of JG , see (1). Hence G has at least two
distinct cut vertices, which are the neighbours of the leaves.
Remark 2.5. Notice that Proposition 2.3 does not hold if G is not bipartite. In fact, there are nonbipartite graphs G with an arbitrary number of leaves and such that JG is Cohen-Macaulay. For n ≥ 2
the binomial edge ideal JKn of the complete graph Kn is Cohen-Macaulay, since it is the ideal of 2-minors
of a generic (2 × n)-matrix (see [3, Corollary 2.8]). Moreover, for n ≥ 3, Kn has 0 leaves. Let W ⊆ [n],
with |W | = k ≥ 1. Adding a whisker to a vertex of W , the resulting graph H has 1 leaf and JH is
Cohen-Macaulay by [18, Theorem 2.7]. Applying the same argument to all vertices of W , we obtain a
graph H ′ with k leaves such that JH ′ is Cohen-Macaulay.
In the remaining part of the section we present a construction, Proposition 2.8, that produces new
examples of unmixed binomial edge ideals. It will also be important in the proof of the main theorem.
If X is a subset of V (G), we define the set of neighbours of the elements of X, denoted NG (X), or
simply N (X), as the set
NG (X) = {y ∈ V (G) : {x, y} ∈ E(G) for some x ∈ X}.
Lemma 2.6. Let G be a bipartite graph with bipartition V1 ⊔ V2 , JG unmixed and let v1 and v2 be the
neighbours of the leaves.
a) If X ⊆ V1 \ {v1 , v2 }, then N (X) is a cut set of G and |N (X)| ≥ |X|.
b) If {v1 , v2 } ∈ E(G), then m = |V1 | = |V2 | and vi has degree m, for i = 1, 2. Moreover, v1 and v2
are the only cut vertices of G.
Proof. a) First notice that N (X) is a cut set. In fact, every element of X is isolated in GN (X) . Let
v ∈ N (X). Then deg(v) ≥ 2, since v1 , v2 ∈
/ X. Adding v to GN (X) , it connects at least a vertex of X with
some other connected component.
Now, suppose by contradiction that |N (X)| < |X|. Then GN (X) has at least |X| isolated vertices and
another connected component containing a leaf, because v1 , v2 ∈
/ X. Hence, cG (N (X)) ≥ |X| + 1 >
|N (X)| + 1, against the unmixedness of JG .

7

b) Assume that v1 ∈ V1 . Then v2 ∈ V2 , since {v1 , v2 } ∈ E(G). By Remark 2.4(i), it follows that
m = |V1 | = |V2 |. Define X = {w ∈ V2 : {v1 , w} ∈
/ E(G)} and assume that X 6= ∅. Since {v1 , v2 } ∈ E(G),
v2 ∈
/ X, hence N (X) is a cut set and |N (X)| ≥ |X| by a). We claim that the inequality is strict. Assume
|N (X)| = |X|. Let f be the leaf of G adjacent to v1 , then S = V2 \ (X ∪ {f }) is a cut set of G and
|S| = m − |X| − 1. In fact, in GS all vertices of V1 \ N (X) are isolated, except for v1 that is connected only
to f . Moreover, by definition of X, if we add an element of S to GS , we join the connected component
of v1 with some other connected component of GS . Thus, S is a cut set and GS consists of at least
|V1 | − |N (X)| − 1 = m − |X| − 1 isolated vertices, the single edge {v1 , f }, and the connected component
containing the vertices of X and N (X). Hence, cG (S) ≥ m − |X| + 1 > |S| + 1, a contradiction since JG
is unmixed. This shows that |N (X)| > |X|.
Now, the vertices of X are isolated in GN (X) . Moreover, the remaining vertices belong to the same
connected component, because, by definition of X, {v1 , w} ∈ E(G) for every w ∈ V2 \ X and all vertices
in V1 \ N (X) are adjacent to vertices of X. Hence, cG (N (X)) = |X| + 1 < |N (X)| + 1, which again
contradicts the unmixedness of JG . Hence, X = ∅ and v1 has degree m. In the same way it follows that
v2 has degree m.
For the last part of the claim, notice that if v ∈ V (G) \ {v1 , v2 }, the first part implies that every vertex
of G{v} is adjacent to either v1 or v2 . Hence, G{v} is connected and, thus, v is not a cut vertex of G. 
Remark 2.7. Let G be a bipartite graph such that JG is unmixed. If G has exactly two cut vertices, they
are not necessarily adjacent. Thus, the converse of the last part of Lemma 2.6 b) does not hold. In fact,
if |V1 | = |V2 | + 1, then v1 and v2 belong to the same bipartition set, hence {v1 , v2 } ∈
/ E(G). On the other
hand, if |V1 | = |V2 |, let G be the graph in Figure 4. One can check with Macaulay2 [7] that the ideal JG
is unmixed, and we notice that the vertices 2 and 11 are the only cut vertices, but {2, 11} ∈
/ E(G).
1

3

5

7

9

11

2

4

6

8

10

12

Figure 4
Proposition 2.8. Let H be a bipartite graph with bipartition V1 ⊔ V2 and |V1 | = |V2 |. Let v and f be two
new vertices and let G be the bipartite graph with V (G) = V (H) ∪ {v, f } and E(G) = E(H) ∪ {{v, x} :
x ∈ V1 ∪ {f }}. If JH is unmixed and the neighbours of the leaves of H are adjacent, then JG is unmixed
and
M(G) = {∅, V1 } ∪ {S ∪ {v} : S ∈ M(H)} ∪ {T ⊂ V1 : T ∈ M(H)}.
Moreover, the converse holds if there exists w ∈ V1 such that degG (w) = 2.
Proof. Assume that JH is unmixed and the neighbours of the leaves of H are adjacent. Clearly, ∅, V1 ∈
M(G). If S ∈ M(H), then adding v to GS∪{v} we join f with some other connected component of
HS . Moreover, if w ∈ S, adding w to GS∪{v} we join at least two connected components of HS (since
S ∈ M(H)), which are different components of GS∪{v} . Finally, let T ∈ M(H), T ⊂ V1 . By Lemma 2.6

8

b), in H there exists a unique cut vertex v2 ∈ V2 and NH (v2 ) = V1 . Hence, adding w ∈ T to GT , we join
at least two components since NG (v) = V1 ∪ {f } and T ∈ M(H).
Conversely, let S ∈ M(G) and suppose first that v ∈ S. Then GS = HS\{v} ⊔ {f } and this implies that
S \ {v} is a cut set of H, since every element of S \ {v} has to join some connected components that only
contain vertices of HS\{v} . Therefore cG (S) = cH (S \ {v}) + 1 = |S| + 1.
Suppose now that v ∈
/ S. Let w be the leaf of H adjacent to v2 , that is also adjacent to v in G. First
of all, notice that S ⊂ V1 . Indeed, in GS every vertex of V1 \ S is in the same connected component
of v. Thus, a vertex of V2 cannot join different connected components. Since w is adjacent only to v
and v2 , if w ∈ S, then v and v2 cannot be in the same connected component of GS . This means that
V1 ⊂ S, because all the vertices of V1 are adjacent to v and v2 , by Lemma 2.6 b). Thus S = V1 and
cG (S) = |V2 | + 1 = |S| + 1. Hence, we may assume that w ∈
/ S. We claim that, in this case, S ∈ M(H).
In fact, it is clear that v2 , w, v and f are in the same connected component C of GS , which also contains
all vertices of V1 \ S, since they are adjacent to v. Then, the connected components of GS and HS are
the same except for C, that in HS is C{v,f } 6= ∅. Therefore, if x ∈ S joins two connected components of
GS , it also joins the same connected components of HS (or C{v,f } , if it joins C), hence S is a cut set of
H. Moreover, cG (S) = cH (S) = |S| + 1.
Conversely, assume that JG is unmixed and let S ∈ M(H). Notice that w is a leaf of H, hence w ∈
/ S,
by Remark 2.1. We prove that T = S ∪ {v} is a cut set of G. As before, GT = HS ∪ {f }. Thus the
elements of S join different connected components also in GT and v connects the isolated vertex f with
the connected component of w. Hence, T ∈ M(G) and cH (S) = cG (T ) − 1 = |T | + 1 − 1 = |S| + 1.
Finally, let vi be the cut vertex of H in Vi for i = 1, 2. Since {v, v1 } ∈ E(G), it follows, from Lemma
2.6 b), that {v1 , v2 } ∈ E(G). Then v1 and v2 are adjacent also in H.

In Figure 5, we show an example of the above construction. The ideal JG is unmixed by Proposition
2.8, since H = M4,4 and JH is unmixed by Example 2.2. Moreover, it will follow from Example 5.4 and
Proposition 5.14 that JG is not Cohen-Macaulay.
v

f
Figure 5
In Proposition 2.8, the existence of a vertex w ∈ V1 such that degG (w) = 2 means that w is a leaf of
H. This is not true in general, see for instance the graph Mk,k in Example 2.2 for k ≥ 4. However, if JH
is unmixed, this always holds:
Corollary 2.9. Let H be a bipartite graph with bipartition V1 ⊔ V2 , |V1 | = |V2 | and such that JH is
unmixed. Let G be the graph in Proposition 2.8. Then JG is unmixed if and only if the neighbours of the
leaves of H are adjacent.
Example 2.10. The graph H of Figure 4 is such that JH is unmixed, but the two cut vertices 2 and
11 are not adjacent. The graph in Figure 6 is the graph G obtained from H with the construction in

9

Proposition 2.8. According to Corollary 2.9, JG is not unmixed: in fact S = N (11) = {8, 10, 12} is a cut
set and cG (S) = 3 6= |S| + 1.
1

3

5

7

9

11

13

2

4

6

8

10

12

14

Figure 6

3. Basic blocks
In this section we study the basic blocks Fm of our classification, proving that JFm is Cohen-Macaulay.
In what follows we will use several times the following argument.
Remark 3.1. Let G be a graph, v be a vertex of G, H ′ = G \ {v} and assume that M(H ′ ) = {S \ {v} :
T
S ∈ M(G), v ∈ S}, in particular v is a cut vertex of G since ∅ ∈ M(H ′ ). Let JG = S∈M(G) PS (G) be
T
T
the primary decomposition of JG and set A = S∈M(G),v∈S
S∈M(G),v∈S PS (G). Then
/ PS (G) and B =
JG = A ∩ B and we have the short exact sequence
0 −→ R/JG −→ R/A ⊕ R/B −→ R/(A + B) −→ 0.

(2)
Notice that

i) A = JH , where H is the graph obtained from G by adding all possible edges between the vertices of
NG (v). In other words, V (H) = V (G) and E(H) = E(G) ∪ {{k, ℓ} : k, ℓ ∈ NG (v), k 6= ℓ}. In fact,
notice that v ∈
/ S for every S ∈ M(H) by Remark 2.1 and all cut sets of G not containing v are
cut sets of H as well. Thus, M(H) = {S ∈ M(G) : v ∈
/ S}. Moreover, for every S ∈ M(H), the
connected components of GS and HS are the same, except for the component containing v, which
ei = H
e i , hence PS (G) = PS (H) for every S ∈ M(H).
is Gi in GS and Hi in HS . Nevertheless, G
′
ii) B = (xv , yv ) + JH ′ , where H = G \ {v}. In fact, if S ∈ M(G) with v ∈ S, then S \ {v} ∈ M(H ′ )
by assumption and we have that PS (G) = (xv , yv ) + PS\{v} (H ′ ). Thus,
\
\
B = (xv , yv ) +
PS\{v} (H ′ ) = (xv , yv ) +
PT (H ′ ) = (xv , yv ) + JH ′ .
S∈M(G),v∈S

T ∈M(H ′ )

iii) A + B = (xv , yv ) + JH ′′ , where H ′′ = H \ {v}.

We now describe a new family of Cohen-Macaulay binomial edge ideals associated with non-bipartite
graphs, which will be useful in what follows. Let Kn be the complete graph on the vertex set [n] and
W = {v1 , . . . , vr } ⊆ [n]. Let H be the graph obtained from Kn by attaching, for every i = 1, . . . , r, a
complete graph Khi to Kn in such a way that V (Kn ) ∩ V (Khi ) = {v1 , . . . , vi }, for some hi > i. We say
that the graph H is obtained by adding a fan to Kn on the set S. For example, Figure 7 shows the result
of adding a fan to K6 on a set S of three vertices.
Lemma 3.2. Let Kn be the complete graph on [n] and W1 ⊔ · · · ⊔ Wk be a partition of a subset W ⊆ [n].
Let G be the graph obtained from Kn by adding a fan on each set Wi . Then JG is Cohen-Macaulay.

10

Figure 7. Adding a fan to K6 on three vertices
Proof. First we show that JG is unmixed. For every i = 1, . . . , k, set Wi = {vi,1 , . . . , vi,ri } and Mi =
{∅} ∪ {{vi,1 , . . . , vi,h } : 1 ≤ h ≤ ri }. We claim that
(3)

M(G) = {T1 ∪ · · · ∪ Tk : Ti ∈ Mi , T1 ∪ · · · ∪ Tk ( [n]}.

Let T = T1 ∪ · · · ∪ Tk 6= ∅, with Ti ∈ Mi for i = 1, . . . , k, and T ( [n]. Let v ∈ T . Then v ∈ Tj
for some j, say v = vj,ℓ , with 1 ≤ ℓ ≤ rj . Hence, if we add v to the graph GT , it joins the connected
component containing Kn \ T (which is non-empty since T ( [n]) with Khj,ℓ \ T , where V (Khj,ℓ ) ∩ V (G) =
{vj,1 , . . . , vj,ℓ }. This shows that cG (T ) > cG (T \ {v}) for every v ∈ T , thus T ∈ M(G).
Conversely, let T ∈ M(G). First notice that T 6= [n], since cG ([n]) = cG ([n] \ {vi,ri }) for every i.
S
Moreover, T does not contain any vertex v ∈ V (G) \ ki=1 Wi , otherwise v belongs to exactly one maximal
S
S
clique of G, see Remark 2.1. Then cG (T ) = cG (T \{v}). Hence T ⊆ ki=1 Wi and T ( [n]. Let T = ki=1 Ti ,
where Ti ⊆ Wi . We want to show that, if vi,j ∈ Ti ⊆ T , then vi,h ∈ T for every 1 ≤ h < j. Assume
vi,h ∈
/ Ti for some h < j. Then cG (T ) = cG (T \ {vi,j }) because all maximal cliques of G containing vi,j
contain vi,h as well, since h < j. This shows that Ti ∈ Mi for every i.
Finally, for every T ∈ M(G), since GT consists of |T | connected components that are complete graphs
(Khj,ℓ \ T for every j = 1, . . . , k and ℓ = 1, . . . , |Tj |) and a graph obtained from Kn \ T by adding a fan on
each Wi \Ti , it follows that cG (T ) = |T |+ 1. This means that JG is unmixed and dim(R/JG ) = |V (G)|+ 1.
In order to prove that JG is Cohen-Macaulay, we proceed by induction on k ≥ 1 and |Sk | ≥ 1. Let
k = 1 and set W1 = {1, . . . , r}. If |W1 | = 1, then the claim follows by [18, Theorem 2.7]. Assume that
|W1 | = r ≥ 2 and the claim true for r − 1. Notice that G = cone(1, G1 ⊔ G2 ), where G1 ∼
= Kh1 −1 (graph
isomorphism) and G2 is the graph obtained from Kn \ {1} by adding a fan on the clique {2, . . . , r}. We
know that JG1 is Cohen-Macaulay by [3, Corollary 2.8] and JG2 is Cohen-Macaulay by induction. Hence,
the claim follows by [18, Theorem 3.8].
Now, let k ≥ 2 and assume the claim true for k − 1. Again, if |Wk | = 1, the claim follows by
induction and by [18, Theorem 2.7]. Assume that |Wk | = rk ≥ 2 and the claim true for rk − 1. For
T
simplicity, let Wk = {1, . . . , rk }. Let JG = S∈M(G) PS (G) be the primary decomposition of JG and set
T
T
A = S∈M(G),1∈S
S∈M(G),1∈S PS (G). Then JG = A ∩ B.
/ PS (G) and B =
By Remark 3.1, A = JH , where H is a complete graph on the vertices of {1} ∪ NG (1) to which we add
a fan on the cliques W1 , . . . , Wk−1 . Hence R/A is Cohen-Macaulay by induction on k and depth(R/A) =
|V (G)| + 1.
Notice that H ′ = G \ {1} is the disjoint union of a complete graph and a graph K ′ , which is obtained
by adding a fan to Kn \ {1} ∼
= Kn−1 on the cliques W1 , . . . , Wk−1 and Wk \ {1}. From (3), it follows

11

that M(H ′ ) = {S \ {1} : S ∈ M(G), 1 ∈ S}, thus B = (x1 , y1 ) + JH ′ by Remark 3.1. By induction on
|Wk |, JK ′ is Cohen-Macaulay, hence JH ′ is Cohen-Macaulay since it is the sum of Cohen-Macaulay ideals
on disjoint sets of variables. In particular, depth(R/B) = |V (H ′ )| + 2 = |V (G)| + 1 (it follows from the
formula for the dimension [10, Corollary 3.4]).
Finally, by Remark 3.1, A + B = (x1 , y1 ) + JH ′′ , where H ′′ = H \ {1}. Hence R/(A + B) is CohenMacaulay by induction on k and depth(R/(A + B)) = |V (G)|.
The Depth Lemma [20, Lemma 3.1.4] applied to the short exact sequence (2) yields depth(R/JG ) =
|V (G)| + 1. The claim follows from the first part, since dim(R/JG ) = |V (G)| + 1.

Notice that the graphs produced by Lemma 3.2 are not generalized block graphs (see [13]) nor closed
graphs if k ≥ 2 (studied in [5]). Hence they form a new family of non-biparite graphs whose binomial edge
ideal is Cohen-Macaulay.
Now we prove that the binomial edge ideals of the graphs Fm (see Figure 1) are Cohen-Macaulay. The
graphs Fm are the basic blocks in our classification, Theorem 6.1.
Recall that, for every m ≥ 1, if n = 2m, Fm is the graph on the vertex set [n] and with edge set
E(Fm ) = {{2i, 2j − 1} : i = 1, . . . , m, j = i, . . . , m} .
Notice that Fm , with m ≥ 2, can be obtained from Fm−1 using the construction of Proposition 2.8.
Proposition 3.3. For every m ≥ 1, JFm is Cohen-Macaulay.
Proof. First we show that JFm is unmixed. We proceed by induction on m ≥ 1. If m = 1, then JF1 is
a principal ideal, hence it is prime and unmixed of height 1. Let m ≥ 2 and assume the claim true for
m − 1. Then Fm is obtained from Fm−1 by adding the vertices n − 1 and n and connecting n − 1 to the
vertices 2, 4, . . . , n. Since JFm−1 is unmixed by induction and {2, n − 3} ∈ E(Fm−1 ), by Proposition 2.8,
it follows that JFm is unmixed and
(4)

M(Fm ) = {∅} ∪ {{2, 4, . . . , 2i} : 1 ≤ i ≤ m − 1} ∪ {{n − 1} ∪ S : S ∈ M(Fm−1 )}.

Now we prove that JFm is Cohen-Macaulay by induction on m ≥ 1. The graphs F1 and F2 are paths,
hence the ideals JF1 and JF2 are complete intersections, by [5, Corollary 1.2], thus Cohen-Macaulay.
T
Let m ≥ 3 and assume that JFm−1 is Cohen-Macaulay. Let JFm = S∈M(Fm ) PS (Fm ) be the primary
T
T
decomposition of JFm and define A = S∈M(Fm ),n−1∈S
/ PS (Fm ) and B =
S∈M(Fm ),n−1∈S PS (Fm ). Then
JFm = A ∩ B.
By Remark 3.1, A = JH , where H is obtained by adding a fan to the complete graph with vertex
set NFm (n − 1) = {2, 4, . . . , n} on the set NFm (n − 1), hence it is Cohen-Macaulay by Lemma 3.2 and
depth(R/A) = n + 1.
Since Fm \ {n − 1} = Fm−1 ⊔ {n}, by (4), M(Fm−1 ⊔ {n}) = {S \ {n − 1} : S ∈ M(Fm ), n − 1 ∈ S}.
Thus, B = (xn−1 , yn−1 ) + JFm−1 ⊔{n} = (xn−1 , yn−1 ) + JFm−1 , hence it is Cohen-Macaulay by induction
and depth(R/B) = n + 1.
Finally, A + B = (xn−1 , yn−1 ) + JH ′′ , where H ′′ = H \ {n − 1}, which is Cohen-Macaulay again by
Lemma 3.2 and depth(R/(A + B)) = n.
The Depth Lemma applied to the exact sequence (2) yields depth(R/JFm ) = n + 1. Moreover, since
JFm is unmixed, it follows that dim(R/JFm ) = n + 1 and, therefore, JFm is Cohen-Macaulay.


12

4. Gluing graphs: operations ∗ and ◦
In this section we consider two operations that, together with the graphs Fm , are the main ingredients
of Theorem 6.1. Given two (not necessarily bipartite) graphs G1 and G2 , we glue them to obtain a
new graph G. If G1 and G2 are bipartite, both constructions preserve the Cohen-Macaulayness of the
associated binomial edge ideal. The first operation is a particular case of the one studied by Rauf and
Rinaldo in [18, Section 2].
Definition 4.1. For i = 1, 2, let Gi be a graph with at least one leaf fi . We define the graph G =
(G1 , f1 ) ∗ (G2 , f2 ) obtained by identifying f1 and f2 (see Figure 8). If it is not important to specify the
vertices fi or it is clear from the context, we simply write G1 ∗ G2 .

f1

f2
f1 = f2
(b) A graph G2

(a) A graph G1

(c) The graph (G1 , f1 ) ∗ (G2 , f2 )

Figure 8
In the next Theorem we recall some results about the operation ∗, see [18, Lemma 2.3, Proposition 2.6,
Theorem 2.7].
Theorem 4.2. For i = 1, 2, consider a graph Gi with at least one leaf fi and G = (G1 , f1 ) ∗ (G2 , f2 ). Let
v1 and v2 be the neighbours of the leaves and let v be the vertex obtained by identifying f1 and f2 . If
A = {S1 ∪ S2 : Si ∈ M(Gi ), i = 1, 2} and
B = {S1 ∪ S2 ∪ {v} : Si ∈ M(Gi ) and vi ∈
/ Si , i = 1, 2},
the following properties hold:
a) M(G) = A ∪ B;
b) JG is unmixed if and only if JG1 and JG2 are unmixed;
c) JG is Cohen-Macaulay if and only if JG1 and JG2 are Cohen-Macaulay.
We now introduce the second operation.
Definition 4.3. For i = 1, 2, let Gi be a graph with at least one leaf fi , vi its neighbour and assume
degGi (vi ) ≥ 3. We define G = (G1 , f1 ) ◦ (G2 , f2 ) to be the graph obtained from G1 and G2 by removing
the leaves f1 , f2 and identifying v1 and v2 (see Figure 9). If it is not important to specify the leaves fi or
it is clear from the context, then we simply write G1 ◦ G2 .
We denote by v the vertex of G resulting from the identification of v1 and v2 and, with abuse of notation,
we write V (G1 ) ∩ V (G2 ) = {v}.
Notice that, if degGi (vi ) = 2 for i = 1, 2, then (G1 , f1 ) ◦ (G2 , f2 ) = (G1 \ {f1 }, v1 ) ∗ (G2 \ {f2 }, v2 ). On
the other hand, we do not allow degG1 (v1 ) = 2 and degG2 (v2 ) ≥ 3 (or vice versa), since in this case the
operation ◦ does not preserve unmixedness, see Remark 4.7 (ii).

13

Remark 4.4. Unlike the operation ∗ (cf. Theorem 4.2), if one of JG1 and JG2 is not Cohen-Macaulay,
then JG1 ◦G2 may not be unmixed, even if G1 and G2 are bipartite. For example, let G1 and G2 be the
graphs in Figure 9(a) and 9(b). Then JG1 ◦G2 is not unmixed even if JG1 = JF4 is Cohen-Macaulay (by
Proposition 3.3) and JG2 = JM4,4 is unmixed (by Example 2.2). In fact, S = {5, 7, 8, 10, 12} ∈ M(G), but
cG (S) = 5 6= |S| + 1.

(a) The graph G1

v1

v2

f1

f2

1

3

5

2

4

6

(b) The graph G2

7

9

11

13

8

10

12

(c) The graph G = G1 ◦ G2

Figure 9
We describe the structure of the cut sets of G1 ◦ G2 under some extra assumption on G1 and G2 . In
this case, ◦ preserves unmixedness.
Theorem 4.5. Let G = G1 ◦ G2 and set V (G1 ) ∩ V (G2 ) = {v}, where degGi (v) ≥ 3 for i = 1, 2. If for
i = 1, 2 there exists ui ∈ NGi (v) with degGi (ui ) = 2, then
(5)

M(G) = A ∪ B,

where
A = {S1 ∪ S2 : Si ∈ M(Gi ), i = 1, 2, v ∈
/ S1 ∪ S2 } and
B = {S1 ∪ S2 : Si ∈ M(Gi ), i = 1, 2, S1 ∩ S2 = {v}}.
If JG1 and JG2 are unmixed and for i = 1, 2 there exists ui ∈ NGi (v) with degGi (ui ) = 2, then JG is
unmixed. The converse holds if G is bipartite. In particular, if G is bipartite and JG is unmixed, the cut
sets of G are described in (5).
Proof. Let S = S1 ∪ S2 ⊂ V (G), where S1 = S ∩ V (G1 ) and S2 = S ∩ V (G2 ). Notice that
(6)

cG (S) = cG1 (S1 ) + cG2 (S2 ) − 1, if v ∈
/ S,

(7)

cG (S) = cG1 (S1 ) + cG2 (S2 ) − 2, if v ∈ S.

In fact, if v ∈
/ S, the connected components of GS are those of (G1 )S 1 and (G2 )S 2 , where the component
containing v is counted once. On the other hand, if v ∈ S, clearly v ∈ S1 ∩S2 and the connected components
of GS are those of (G1 )S 1 and (G2 )S 2 , except for the two leaves f1 and f2 .
In order to prove (5), we show the two inclusions.
⊆: Let S ∈ M(G) and define S1 and S2 as before. Suppose by contradiction that S1 ∈
/ M(G1 ), i.e.,
there exists w ∈ S1 such that cG1 (S1 ) = cG1 (S1 \ {w}). If v ∈
/ S, then by (6)
cG (S \ {w}) = cG1 (S1 \ {w}) + cG2 (S2 ) − 1 = cG1 (S1 ) + cG2 (S2 ) − 1 = cG (S),
a contradiction. On the other hand, if v ∈ S and w 6= v, by (7) we have
cG (S \ {w}) = cG1 (S1 \ {w}) + cG2 (S2 ) − 2 = cG1 (S1 ) + cG2 (S2 ) − 2 = cG (S),

14

again a contradiction. We show that the case w = v cannot occur. In fact, by assumption, there exists
u1 ∈ NG1 (v) such that degG1 (u1 ) = 2. Since v ∈ S, we have that cG (S) = cG (S \ {u1 }), hence u1 ∈
/ S.
,
we
join
the
connected
component
of
u1
Thus cG1 (S1 ) > cG1 (S1 \ {v}), because by adding v to (G1 )S 1
and the isolated vertex f1 , which is a leaf in G1 . Hence w 6= v. The same argument also shows that
S2 ∈ M(G2 ).
⊇: Let S = S1 ∪ S2 , with Si ∈ M(Gi ), for i = 1, 2. Assume first S1 ∩ S2 = {v}. By the equalities (6)
and (7) we have
cG (S \ {v}) = cG1 (S1 \ {v}) + cG2 (S2 \ {v}) − 1 ≤ cG1 (S1 ) + cG2 (S2 ) − 3 = cG (S) − 1 < cG (S).
Let w ∈ S, w 6= v. Without loss of generality, we may assume w ∈ S1 . Then
cG (S \ {w}) = cG1 (S1 \ {w}) + cG2 (S2 ) − 2 ≤ cG1 (S1 ) + cG2 (S2 ) − 3 = cG (S) − 1 < cG (S).
Assume now that v ∈
/ S1 ∪ S2 . Let w ∈ S, and without loss of generality w ∈ S1 . Then
cG (S \ {w}) = cG1 (S1 \ {w}) + cG2 (S2 ) − 1 ≤ cG1 (S1 ) + cG2 (S2 ) − 2 = cG (S) − 1 < cG (S).
Let now JG1 and JG2 be unmixed and for i = 1, 2 there exists ui ∈ NGi (v) with degGi (ui ) = 2. By the
last assumption, the cut sets of G are described in (5). Let S ∈ M(G) and Si = S ∩ V (Gi ) for i = 1, 2.
Thus, by (6) and (7),
(i) if v ∈
/ S, cG (S) = cG1 (S1 ) + cG2 (S2 ) − 1 = |S1 | + 1 + |S2 | + 1 − 1 = |S1 | + |S2 | + 1 = |S| + 1,
(ii) if v ∈ S, cG (S) = cG1 (S1 ) + cG2 (S2 ) − 2 = |S1 | + 1 + |S2 | + 1 − 2 = |S1 | + |S2 | = |S| + 1.
It follows that JG is unmixed.
Conversely, let JG be unmixed and G bipartite. If S is a cut set of G1 , then it is also a cut set of G
and clearly cG1 (S) = cG (S); therefore JG1 is unmixed and the same holds for JG2 . By Proposition 2.3,
the graphs G, G1 and G2 have exactly two leaves. Let fi be the leaf of Gi adjacent to v and gi be the
other leaf of Gi . Thus, g1 and g2 are the leaves of G.
By symmetry, it is enough to prove that there exists u1 ∈ NG1 (v) such that degG1 (u1 ) = 2. For i = 1, 2,
let V (Gi ) = Vi ∪ Wi and assume |V1 | ≤ |W1 |. By Remark 2.4, we have one of the following two cases:
a) if |V1 | = |W1 |, we may assume f1 ∈ W1 and g1 ∈ V1 . Set S = (W1 \ {f1 }) ∪ {v}. Hence,
cG1 (S) = |V1 | = |W1 | = |S|.
b) If |W1 | = |V1 | + 1, then f1 , g1 ∈ W1 . Hence v ∈ V1 . Set S = (W1 \ {f1 , g1 }) ∪ {v}. Thus,
cG1 (S) = |V1 | = |W1 | − 1 = |S|.
First suppose |V (G2 )| even and assume f2 ∈ W2 . Hence, v, g2 ∈ V2 and T = V2 \ {g2 } is a cut set of G2 .
Now, let |V (G2 )| be odd and assume f2 ∈ W2 . Hence, g2 ∈ W2 , v ∈ V2 and |W2 | = |V2 | + 1. Then
T = V2 is a cut set of G2 .
In both cases, notice that S ∪ T is not a cut set of G, since S ∩ T = {v} and, by (7),
cG (S ∪ T ) = cG1 (S) + cG2 (T ) − 2 = |S| + |T | − 1 = |S ∪ T |,
which contradicts the unmixedness of JG . Let u ∈ S ∪ T such that cG ((S ∪ T ) \ {u}) = cG (S ∪ T ) = |S ∪ T |.
We show that u ∈ S and u 6= v. If u ∈
/ S, then u ∈ T and u 6= v. By (7),
cG ((S ∪ T ) \ {u}) = cG1 (S) + cG2 (T \ {u}) − 2 < |S| + cG2 (T ) − 2 = |S| + |T | − 1 = |S ∪ T | = cG (S ∪ T ),

15

against our assumption (the inequality holds since T is a cut set of G2 and the second equality follows
from the unmixedness of JG2 ). Thus, u ∈ S. Moreover, in both cases cG1 (S \ {v}) = cG1 (S) = |S| (since
v is a leaf of (G1 )S\{v} ) and, by (6),
cG ((S∪T )\{v}) = cG1 (S\{v})+cG2 (T \{v})−1 = |S|+|T |−|NG2 (v)|+2−1 < |S|+|T |−1 = |S∪T | = cG (S∪T ),
where the inequality holds since degG2 (v) ≥ 3. This contradicts our assumption, thus u 6= v.
We conclude that u ∈ S \ {v}. Since u 6= f1 , g1 , we have degG1 (u) ≥ 2. On the other hand, since
cG ((S ∪ T ) \ {u}) = cG (S ∪ T ), it follows that u ∈ NG1 (v) and degG1 (u) = 2.

Corollary 4.6. Let G = Fm1 ◦ · · · ◦ Fmk , where mi ≥ 3 for i = 1, . . . , k. Then JG is unmixed.
Proof. Set G1 = Fm1 ◦ · · · ◦ Fmk−1 , G2 = Fmk and let v be the only vertex of V (G1 ) ∩ V (G2 ). We proceed
by induction on k ≥ 2. If k = 2, the claim follows by Theorem 4.5, because JG1 and JG2 are unmixed by
Proposition 3.3 and for i = 1, 2, there exists ui ∈ NGi (v) such that degGi (ui ) = 2, by definition of Fmi .
Now let k > 2 and assume the claim true for k − 1. By induction, JG1 is unmixed. Since mk−1 ≥ 3,
there exists u1 ∈ NG1 (v) such that degG1 (u1 ) = 2. The claim follows again by Theorem 4.5.

Remark 4.7. In Corollary 4.6 the condition mi ≥ 3, for i = 2, . . . , k − 1, cannot be omitted. For
instance, the binomial edge ideal JF3 ◦F2 ◦F3 is not unmixed: in fact S = {3, 5, 6, 8} is a cut set and
cF3 ◦F2 ◦F3 (S) = 4 6= |S| + 1, see Figure 10.
1

3

5

7

9

2

4

6

8

10

Figure 10. The graph F3 ◦ F2 ◦ F3
On the other hand, we may allow m1 = mk = 2, since, in this case, the graph G = Fm1 ◦ · · · ◦ Fmk =
F1 ∗ Fm2 ◦ · · · ◦ Fmk−1 ∗ F1 . Hence, JG is unmixed by Theorem 4.2 and Corollary 4.6.
Let n ≥ 3, W1 ⊔ · · · ⊔ Wk be a partition of a subset of [n] and Wi = {vi,1 , . . . , vi,ri } for some ri ≥ 1 and
i = 1, . . . , k. Let E be the graph obtained from Kn by adding a fan on each set Wi in such a way that
we attach a complete graph Kh+1 to Kn , with V (Kn ) ∩ V (Kh+1 ) = {vi,1 , . . . , vi,h }, for i = 1, . . . , k and
h = 1, . . . , ri , see Figure 11 (cf. Figure 7). By Lemma 3.2, JE is Cohen-Macaulay.
Lemma 4.8. Let G = Fm1 ◦· · ·◦Fmk ◦E, where E is the graph defined above, mi ≥ 3 for every i = 2, . . . , k
and V (Fm1 ◦ · · · ◦ Fmk ) ∩ V (E) = {v}. Assume that v ∈ W1 and |W1 | ≥ 2. Then JG is unmixed.
Proof. Set G1 = Fm1 ◦ · · · ◦ Fmk and G2 = E. Then JG1 is unmixed by Corollary 4.6 and JG2 is CohenMacaulay by Lemma 3.2, hence it is unmixed.
Notice that, since mk ≥ 3, there exists u1 ∈ NG1 (v) such that degG1 (u1 ) = 2. Moreover, since
|W1 | ≥ 2 and by definition of G2 = E, we attach K3 to Kn in such a way that |V (Kn ) ∩ V (K3 )| = 2
and v ∈ V (Kn ) ∩ V (K3 ). Thus, there exists u2 ∈ K3 , hence u2 ∈ NG2 (v), such that degG2 (u2 ) = 2. The
statement follows by Theorem 4.5.


16

Figure 11. The graph E
In Lemma 4.8 we assume |W1 | ≥ 2, since this is the only case we need in the following theorem.
Moreover, in the next statement the case F = E is useful to prove that the binomial edge ideal associated
with Fm1 ◦ · · · ◦ Fmk ◦ Fn is Cohen-Macaulay.
Theorem 4.9. Let G = Fm1 ◦ · · · ◦ Fmk ◦ F , where mi ≥ 3 for every i = 1, . . . , k and F = Fn for some
n ≥ 3 or F = E is the same graph of Lemma 4.8. Then JG is Cohen-Macaulay.
Proof. Let V (Fm1 ◦· · ·◦Fmk )∩V (F ) = {w} and call fk and f the leaves that we remove from Fm1 ◦· · ·◦Fmk
T
T
and F . Let JG = S∈M(G) PS (G) be the primary decomposition of JG and set A = S∈M(G),w∈S
/ PS (G)
T
and B = S∈M(G),w∈S PS (G).
We proceed by induction on k ≥ 1. First assume k = 1 and, for simplicity, let m = m1 . By Remark
3.1, the ideal A is the binomial edge ideal of the graph H, obtained by adding a fan to the complete graph
with vertex set {w} ∪ NG (w) on the sets NFm (w) \ {fk } and NF (w) \ {f }. Hence R/A is Cohen-Macaulay
and depth(R/A) = |V (G)| + 1 by Lemma 3.2.
Notice that G \ {w} = (Fm \ {w, fk }) ⊔ (F \ {w, f }). By Theorem 4.5 and Remark 3.1, B = (xw , yw ) +
JFm \{w,fk } + JF \{w,f } , where Fm \{w, f } ∼
= Fm−1 . Moreover, if F = E, E \{w, f } is of the same form as E,
∼
otherwise F = Fn and Fn \ {w, f } = Fn−1 . In any case, JFm \{w,fk } and JF \{w,f } are Cohen-Macaulay (by
Lemma 3.2 and Proposition 3.3), hence B is Cohen-Macaulay since it is the sum of Cohen-Macaulay ideals
on disjoint sets of variables. In particular, it follows from the formula for the dimension [10, Corollary 3.4]
that depth(R/B) = |V (Fm−1 )| + 1 + |V (F \ {w, f })| + 1 = |V (G)| + 1.
Finally, A + B = (xw , yw ) + JH ′′ , where H ′′ = H \ {w} is the binomial edge ideal of the graph obtained
by adding a fan to the complete graph with vertex set NG (w) on the sets NFm (w) \ {fk } and NF (w) \ {f }.
Hence R/(A + B) is Cohen-Macaulay and depth(R/(A + B)) = |V (G)| by Lemma 3.2.
The Depth Lemma applied to the short exact sequence (2) yields depth(R/JG ) = |V (G)| + 1. The claim
follows by Lemma 4.8 (resp. Corollary 4.6), since dim(R/JG ) = |V (G)| + 1.
Now let k > 1 and assume the claim true for k − 1. By Remark 3.1, the ideal A is the binomial edge
ideal of the graph H = F1 ◦ · · · ◦ Fmk−1 ◦ F ′ , where F ′ is obtained by adding a fan to the complete graph
with vertex set {w} ∪ NG (w) on the sets NFmk (w) \ {fk } and NF (w) \ {f }. Notice that, since mk ≥ 3,
|NFmk (w) \ {fk }| ≥ 2 and we are in the assumption of Lemma 4.8. Hence, R/A is Cohen-Macaulay by
induction and depth(R/A) = |V (G)| + 1.
Similarly to the case k = 1, the ideal B equals (xw , yw ) + J(Fm1 ◦···◦Fmk )\{w,fk } + JF \{w,f } , where (Fm1 ◦
· · · ◦ Fmk ) \ {w, fk } ∼
= Fm1 ◦ · · · ◦ Fmk −1 and JFm1 ◦···◦Fmk −1 is Cohen-Macaulay by induction (notice that,
if mk = 3, then Fm1 ◦ · · · ◦ Fmk = Fm1 ◦ · · · ◦ Fmk−1 ∗ F1 and the corresponding binomial edge ideal is

17

Cohen-Macaulay by induction and Theorem 4.2). Moreover, if F = E, then E \ {w} is of the same form
as E, otherwise F = Fn and Fn \ {w, f } ∼
= Fn−1 . Thus JF \{w,f } is Cohen-Macaulay (by Lemma 3.2 and
Proposition 3.3), hence B is Cohen-Macaulay since it is the sum of Cohen-Macaulay ideals on disjoint sets
of variables. In particular, depth(R/B) = |V (Fm−1 )| + 1 + |V (F \ {w, f })| + 1 = |V (G)| + 1 (it follows
from the formula for the dimension [10, Corollary 3.4]).
Finally, A+ B = (xw , yw )+ JH ′′ , where H ′′ = H \{w} (again, since mk ≥ 3, we have |NFmk (w)\{fk }| ≥
2). Hence R/(A + B) is Cohen-Macaulay by induction and depth(R/(A + B)) = |V (G)|.
The Depth Lemma applied to the short exact sequence (2) yields depth(R/JG ) = |V (G)| + 1. Notice
that, if F = E, the ideal JG is unmixed by Lemma 4.8, whereas, if F = Fn , it is unmixed by Corollary
4.6. This implies that dim(R/JG ) = |V (G)| + 1 and the claim follows.

5. The dual graph of binomial edge ideals
In this section we study the dual graph of binomial edge ideals. This is one of the main tools to prove
that, if G is bipartite and JG is Cohen-Macaulay, then G can be obtained recursively via a sequence of
operations ∗ and ◦ on a finite set of graphs of the form Fm , Theorem 6.1 c).
Let I be an ideal in a polynomial ring A = K[x1 , . . . , xn ] and let p1 , . . . , pr be the minimal prime ideals
of I. Following [2], the dual graph D(I) of I is a graph with vertex set {1, . . . , r} and edge set
{{i, j} : ht(pi + pj ) − 1 = ht(pi ) = ht(pj ) = ht(I)}.
Notice that, if D(I) is connected, then I is unmixed. In [8], Hartshorne proved that if A/I is CohenMacaulay, then D(I) is connected. We will show that this is indeed an equivalence for binomial edge ideals
of bipartite graphs. Nevertheless, this does not hold when G is not bipartite, see Remark 5.1.
To ease the notation, we denote by D(G) the dual graph of the binomial edge ideal JG of a graph G.
Moreover, we denote by PS (G) or PS both the minimal primes of JG and the vertices of D(G).
Remark 5.1. The dual graph of the non-bipartite graph G in Figure 12(a) is connected, see Figure 12(b),
but using Macaulay2 [7] one can check that JG is not Cohen-Macaulay.
P{3,5}
3
8

2

4

P{2,5}

P∅

7
5

P{3,4,5}

P{5}

1

P{2}

6

(a) The graph G

P{3,4}
P{2,3,4}

P{2,4}
(b) The dual graph of G

Figure 12
We now describe the edges of the dual graph of JG , when JG is unmixed. This result holds for nonbipartite graphs as well.

18

Theorem 5.2. Let G be a graph such that JG is unmixed and let S, T ∈ M(G), with |T | ≥ |S|. Denote
by PS the minimal primes of JG . Then the following properties hold:
a) if |T \ S| > 1, then {PS , PT } is not an edge of D(G);
b) if |T \ S| = 1 and S ⊂ T , then {PS , PT } is an edge of D(G);
c) if T \ S = {t} and S * T , then {PS , PT } is an edge of D(G) if and only if t is not a cut vertex of
GS .
Proof. Let E1 , E2 , . . . , Ec(S) be the connected components of GS .
a) Let v, w ∈ T \ S. Then PS + PT ⊇ PS + (xv , xw , yv , yw ). If Ej and Ek are the connected components
of GS containing v and w respectively (possibly j = k), it follows that


PS + (xv , xw , yv , yw ) = 

[

{xi , yi }, JEe1 , . . . , J(Eej )

{v}

i∈S∪{v,w}

, . . . , J(Ee

k ){w}

. . . , JEe

c(S)



.

Thus, ht(PS + PT ) ≥ ht(PS + (xv , xw , yv , yw )) = ht(PS ) + 4 − 2 = ht(PS ) + 2. Hence, {PS , PT } is not an
edge of D(G).
b) Let T \ S = {t} and let Ej be the connected component of GS containing t. Then
PS + PT =

[

{xi , yi }, (xt , yt ), JEe1 , . . . , J(Eej )

{t}

i∈S

, . . . , JEe

c(S)

!

.

Thus, ht(PS + PT ) = ht(PS ) + 2 − 1 = ht(PS ) + 1. Hence, {PS , PT } is an edge of D(G).
c) Let G1 , G2 , . . . , Gr be the connected components of GS∩T . Let also S \ T = {s}, T \ S = {t} and
assume that s ∈ Gj and t ∈ Gk . Since S, T ∈ M(G), it follows that s and t are cut vertices of Gj and
Gk , respectively.
If j 6= k, then t is a cut vertex of GS . Moreover, if V (Gj ) = V (E1 ∪ · · · ∪ Eh ∪ {s}), where h ≥ 2 and
Gk = Eh+1 , then


PS + PT = 

[

i∈S∪{t}

{xi , yi }, J(Gej )

{s}

, J(Ee

h+1 ){t}

, JEe

h+2

, . . . , JEe

c(S)



.

P
It follows that ht(PS +PT ) = ht(PS )+2+|V (Gj )|−2− hi=1 (|V (Ei )|−1)−1 = ht(PS )+2+1−2+h−1 =
ht(PS ) + h > ht(PS ) + 1. Thus, {PS , PT } is not an edge of D(G).
Assume now that j = k and let j = 1 for simplicity. Denote by H1 , . . . , Hi the connected components of
(G1 ){s} and by K1 , . . . , Ki the connected components of (G1 ){t} (note that the number of components is
the same because S, T ∈ M(G) and JG is unmixed). Suppose also that t ∈ H1 and s ∈ K1 . If there exists
v ∈ Hp ∩ Kq with p, q 6= 1, then, since v ∈ Hp , there exists a path from v to s that does not involve t. This
is a contradiction because v ∈ Kq and s ∈ K1 . Hence, Kq ⊆ H1 and Hp ⊆ K1 for all p, q = 2, . . . , i. In
particular, the connected components of GS∪T are H2 , . . . , Hi , K2 , . . . , Ki , G2 , . . . , Gr and the connected
components of H1 ∩ K1 , if it is not empty.

19

Suppose first that H1 ∩K1 = ∅. Hence, V (H1 ) = V (K2 ∪· · ·∪Ki ∪{t}) and V (K1 ) = V (H2 ∪· · ·∪Hi ∪{s}).
If i ≥ 3, then t is a cut vertex of H1 , hence a cut vertex of GS . It follows that
!
[
PS =
and
{xh , yh }, JHe1 , JHe2 , . . . , JHei , JGe2 , . . . , JGer
h∈S



PS + PT = 

[

{xh , yh }, J(He1 )

{t}

h∈S∪{t}

, J(Ke 1 )

{s}



, JGe2 , . . . , JGer  .

P
P
Therefore, ht(PS +PT ) = ht(PS )+2−1− ih=2 (|V (Hh )|−1)+|V (K1 )|−2 = ht(PS )+1− ih=2 |V (Hh )|+
P
(i − 1) + ( ih=2 |V (Hh )| + 1) − 2 = ht(PS ) + i − 1 > ht(PS ) + 1, since i ≥ 3. Thus, {PS , PT } is not an
edge of D(G).
On the other hand, if i = 2, then t is not a cut vertex of H1 , since K2 is connected. Therefore, t is not
a cut vertex of GS . It follows that


[
{xh , yh }, J(He1 ) , JHe 2 , JGe2 , . . . , JGer  .
PS + PT = 
{t}

h∈S∪{t}

Hence, ht(PS + PT ) = ht(PS ) + 2 − 1 = ht(PS ) + 1 and {PS , PT } is an edge of D(G).
Let now H1 ∩ K1 6= ∅. It follows that
V (H1 ) = V (K2 ∪ · · · ∪ Ki ∪ (H1 ∩ K1 ) ∪ {t}) and

V (K1 ) = V (H2 ∪ · · · ∪ Hi ∪ (H1 ∩ K1 ) ∪ {s})

and in this case t is a cut vertex of GS . Moreover,

[
{xh , yh }, J(He1 )
PS + PT = 

{t}

h∈S∪{t}

In fact, JHe ⊆ J(Ke 1 )
h

J(He1 )

{t}

{s}

+J(Ke 1 )

{s}

and JKe ⊆ J(He1 )
h

{t}

, J(Ke 1 )

{s}



, JGe2 . . . , JGer  .

for all h = 2, . . . , i. We now compute the height of J =

. Setting W1 = H2 ∪· · ·∪Hi and W2 = K2 ∪· · ·∪Ki , the ideal J is the binomial edge ideal

f1 ∪ W
f2 ∪(H
e1 ∩K
e 1 ) by adding the edges {{v, w} : v ∈ H
e1 ∩K
e 1, w ∈ W
f1 ∪ W
f2 }.
of the graph F obtained from W
e1 ∩ K
e 1 . Moreover,
It is easy to check that the only cut sets of F are ∅ and H
e1 ∩ K
e 1 )| − 2 ≥ |V (F )| − 1 = ht(P∅ (F ))
ht(PHe1 ∩Ke 1 (F )) = |V (F )| + |V (H

Thus ht(J) = |V (F )| − 1 =

Pi

f1 )| + |V (W
f2 )| + |V (H
e1 ∩ K
e 1 )| − 1.
= |V (W

h=1 |V

ht(PS + PT ) = ht(PS ) + 2 −

(Hh )| − 2. Since i ≥ 2, we get

i
X

(|V (Hh )| − 1) +

h=1

Hence, {PS , PT } is not an edge of D(G).

i
X

|V (Hh )| − 2 = ht(PS ) + i > ht(PS ) + 1.

h=1



Remark 5.3. Recall that a graph is k-connected if it has more than k vertices and the removal of any
h < k vertices does not disconnect the graph. In particular, every non-empty connected graph, which is
not reduced to a single vertex, is 1-connected.
Let G be a connected graph such that D(G) is connected. If G is not the complete graph, then G is
1-connected but not 2-connected. In fact, if G is 2-connected, then G does not have cut vertices and, by

20

Theorem 5.2 a), it follows that P∅ is an isolated vertex of the dual graph D(G), a contradiction. Notice
that, if G is bipartite, by Lemma 2.3, it is enough to require JG to be unmixed. Nevertheless, in the
non-bipartite case we need to assume D(G) connected. In fact, the graph G in Figure 13 is 2-connected,
JG is unmixed and D(G) consists of two isolated vertices.
We also observe that the above statement generalizes [1, Proposition 3.10], since having a connected
dual graph is a weaker condition (see also [8, Corollary 2.4]). In particular, being not 2-connected is a
necessary condition for JG to be Cohen-Macaulay.

Figure 13. A 2-connected graph G with JG unmixed and D(G) disconnected
Example 5.4. For every k ≥ 4, let Mk,k and Mk−1,k be the graphs defined in Example 2.2. With the
same notation used there and by Theorem 5.2, their dual graphs are represented in Figure 14.
P{2}

PV1 \{1}
P{2,2k−1}

P∅
P{2k−1}

PV2 \{2k}

(a) The dual graph of JMk,k

P{2}
P∅

P{3,5}

P{2,6} P{2,4,6}
P{6}

(b) The dual graph of JM3,4

P{2}

PV1 \{1,2k−1}
P{2,2k−2}

P∅
P{2k−2}

PV2

(c) The dual graph of JMk−1,k , k ≥ 5

Figure 14
Thus, JMk,k and JMk−1,k are not Cohen-Macaulay by Hartshorne’s Theorem [8]. Notice that, M3,4 is
the bipartite graph with the smallest number of vertices whose binomial edge ideal is unmixed and not
Cohen-Macaulay.
The following technical result has several crucial consequences, see Theorem 5.7 and Theorem 5.8. We
show that, under some assumption on the graph, the intersection of two cut sets, which differ by one
element and have the same cardinality, is again a cut set.
Lemma 5.5. Let G be a graph such that JG is unmixed. Let S, T ∈ M(G) with |S| = |T | and |S \ T | = 1.
(i) If {PS , PT } ∈ D(G), then S ∩ T ∈ M(G).
(ii) If S ∪ T ∈ M(G) and G is bipartite, then S ∩ T ∈ M(G).
Proof. Let S = (T \ {t}) ∪ {s} and let G1 , . . . , Gr be the connected components of GS∩T . Suppose first
that s ∈ Gi and t ∈ Gj with i 6= j. Let z ∈ S ∩ T such that cG ((S ∩ T ) \ {z}) = cG (S ∩ T ). Since z ∈ S and

21

S ∈ M(G), z joins at least two components of GS . Then in GS it is only adjacent to some components of
(Gi ){s} . This implies that it does not join any components in GT , a contradiction, since T ∈ M(G).
Assume now that s, t ∈ G1 and suppose first that r = |S ∩ T | + 1. We claim that S ∩ T ∈ M(G). In
this case, GS has r + 1 connected components, say H1 , H2 , G2 , . . . , Gr . Consider the set
Z = {z ∈ S ∩ T : adding z to GS it connects only H1 and H2 }.
We show that X = (S ∩ T ) \ Z ∈ M(G). For every x ∈ X, we know that cG (S \ {x}) < cG (S). In
particular, adding x to GS , it joins some connected components and at least one of them is Gi with i ≥ 2.
Hence, cG (X \ {x}) < cG (X). Moreover, cG (X) = |S ∩ T | − |Z| + 1, by the unmixedness of JG . On the
other hand, by definition of Z and since S ∈ M(G), it follows that cG (X) = r = |S| = |S ∩ T | + 1. Thus,
Z = ∅ and S ∩ T = X ∈ M(G).
Suppose now that H1 , . . . , Hi , G2 , . . . , Gr are the connected components of GS , with i ≥ 3, and that
t ∈ H1 . In the same way let K1 , . . . , Ki , G2 , . . . , Gr be the connected components of GT and let s ∈ K1 .
We show that this case cannot occur.
Following the same argument of the proof of Theorem 5.2 c), we conclude that the connected components
of GS∪T are H2 , . . . , Hi , K2 , . . . , Ki , G2 , . . . , Gr and the connected components of H1 ∩K1 , if it is not empty.
(i) If H1 ∩ K1 6= ∅, it follows that V (H1 ) = V (K2 ∪ · · · ∪ Ki ∪ (H1 ∩ K1 ) ∪ {t}) and V (K1 ) =
V (H2 ∪ · · · ∪ Hi ∪ (H1 ∩ K1 ) ∪ {s}). In this case, t is a cut vertex of GS , hence {PS , PT } is not an edge of
D(G) by Theorem 5.2 c), a contradiction.
Let now H1 ∩ K1 = ∅, then V (H1 ) = V (K2 ∪ · · · ∪ Ki ∪ {t}) and V (K1 ) = V (H2 ∪ · · · ∪ Hi ∪ {s}). Since
i ≥ 3, t is a cut vertex of H1 , hence {PS , PT } is not an edge of D(G) by Theorem 5.2 c), a contradiction.
(ii) In this case, since both S and S ∪ T are cut sets of G and i ≥ 3, we have that i = 3 and H1 ∩ K1 = ∅.
Therefore, the connected components of GS∪T are H2 , H3 , K2 , K3 , G2 , . . . , Gr .
We know that s is adjacent to x ∈ H1 and that s ∈ K1 . Hence, s is not adjacent to any vertices of K2
or K3 . Thus, x = t, since V (H1 ) = V (K2 ∪ K3 ∪ {t}). This means that {s, t} ∈ E(G). Let
Z = {z ∈ S ∩ T : adding z to GS∪T it connects only some Hi with some Kj }.
Notice that, there are no vertices in S ∩ T that only connects H2 to H3 or K2 to K3 in GS∪T . In fact, if
z ∈ S ∩ T only connects H2 to H3 in GS∪T , then cG (T \ {z}) = cG (T ), a contradiction, since T ∈ M(G).
The same holds for K2 and K3 .
As above, since S ∪ T ∈ M(G), it follows that (S ∩ T ) \ Z ∈ M(G) and, by the unmixedness of JG ,
|Z| = 1, say Z = {z}. Without loss of generality, we may assume that z connects at least H2 and K2 .
Since s and t are adjacent in G, one of them is in the same bipartition set of z. Without loss of
generality, assume that this vertex is t, thus NH2 (s) ∩ NH2 (z) = ∅. Let
A = {x ∈ S ∩ T : if {x, v} ∈ E(G) for some v ∈ G1 , then v ∈ NH2 (s)}.
Notice that, A contains also all vertices of S ∩ T that connect only some Gj ’s in GS∩T , with j ≥ 2. We
claim that
W = ((S ∩ T ) \ A) ∪ NH2 (s) ∈ M(G).
In Figure 15 the set W is colored in gray and the circles represent the connected components of GS∪T ,
where only some vertices are drawn.

22
z ∈Z

K2
(S ∩ T )\(A ∪ B ∪ {z})

H2

w1

NH2 (s)

x2 ∈ A

w2

x1 ∈ A

s

···

t
G2
K3

H3

Gr

y∈B

Figure 15. The set W in gray
Notice that z ∈ W . Let w ∈ W . Adding w = z to GW , we connect a vertex of H2 \ NH2 (s) with K2
whereas, adding w ∈ NH2 (s) to GW , we connect s to H2 \ NH2 (s). Moreover, if w ∈ (S ∩ T ) \ (A ∪ {z}),
we know that, in GS∩T , w connects Gi for some i ≥ 2 to a vertex v of G1 \ NH2 (s). By construction, in
GW the connected components containing v and Gi are different and w still connects them. This proves
that W ∈ M(G).
Since JG is unmixed, we have that cG (W ) = |W | + 1 and a connected component of GW is the subgraph
induced on H3 ∪ K2 ∪ K3 ∪ {s, t}. Thus, removing t from GW , this component splits in three components,
H3 ∪ {s}, K2 , K3 . Therefore, if W ∪ {t} is a cut set of G, we get cG (W ∪ {t}) = cG (W ) + 2 = |W | + 3,
which contradicts the unmixedness of JG .
Hence, we may assume that W ∪ {t} ∈
/ M(G). Thus there exists y ∈ NG (t) that joins t with only one
connected component of GW (i.e., cG ((W ∪ {t}) \ {y}) = cG (W ∪ {t})). In this case, we define
B = {y ∈ S ∩ T : {y, t} ∈ E(G) and NG (y) \ {t} is contained in one connected component of GW },
where |B| ≥ 1, since W ∪ {t} ∈
/ M(G). We claim that
W ′ = (W \ B) ∪ {t} ∈ M(G).
Notice that z ∈ W ′ . The proof is similar to the case of W . We only notice that, adding t to GW ′ , we
connect at least K2 , K3 and the connected component containing s. Moreover, each element in B does
not connect different connected components of GW and any two elements of B are not adjacent (since
they are adjacent to t and G is bipartite). Thus, |W ′ | < |W ∪ {t}| and
cG (W ′ ) = cG (W ∪ {t}) = cG (W ) + 2 = |W | + 3 = |W ∪ {t}| + 2 > |W ′ | + 1,
which contradicts the unmixedness of JG .



Remark 5.6. It could be true that, if G is bipartite and JG is unmixed, then S ∩ T ∈ M(G) for every
S, T ∈ M(G). Both assumptions are needed: in fact, if G is the graph in Figure 16, one can check with
Macaulay2 [7] that JG is Cohen-Macaulay and thus D(G) is connected. Nevertheless, {2, 4}, {4, 5} ∈ M(G)
and {2, 4} ∩ {4, 5} = {4} ∈
/ M(G).

23

On the other hand, if G is the cycle of length 6 with consecutive labelled vertices, then JG is not
unmixed, {1, 3}, {1, 5} ∈ M(G) and {1, 3} ∩ {1, 5} = {1} ∈
/ M(G).
3

2
7

4

P{2}

1
P∅

5

6

P{2,4}

P{2,5}

P{5}

P{2,4,5}

P{4,5}

(a) The graph G
(b) The dual graph of G

Figure 16
The next result is important for Theorem 6.1, since at the same time provides the equivalence b) ⇔ d)
and has important consequences for the proof of b) ⇒ c).
Theorem 5.7. Let G be a bipartite graph. If D(G) is connected, then for every non-empty S ∈ M(G),
there exists s ∈ S such that S \ {s} ∈ M(G).
Proof. By contradiction, let T ∈ M(G) such that T \ {t} ∈
/ M(G) for every t ∈ T . Notice that |T | ≥ 2,
otherwise T \ {t} = ∅ ∈ M(G).
Let W ∈ M(G), W 6= T , such that there exists a path P : PT = PS0 , PS1 , . . . , PSk , PSk+1 = PW in
D(G). Assume P is a shortest path from PT to PW .
Claim: For 1 ≤ i ≤ k + 1, |Si | > |Si−1 |. In particular, |W | > |T |.
We proceed by induction on k ≥ 0.
Let k = 0. First notice that |W | ≥ |T |, otherwise by Theorem 5.2 a), W = T \ {t} ∈ M(G) for some
t ∈ T , a contradiction. If |W | = |T |, since {PT , PW } is an edge of D(G), by Theorem 5.2 a), we have that
W = (T \ {t}) ∪ {w}, for some t ∈ T and w ∈
/ T . By Lemma 5.5, we have that W ∩ T = T \ {t} ∈ M(G),
a contradiction. Then |W | > |T |.
Let k ≥ 1. By induction, |Si | > |Si−1 |, for every 1 ≤ i ≤ k. In particular, by Theorem 5.2 b),
Si = T ∪ {s1 , . . . , si } for i = 1, . . . , k and sj ∈
/ T , for j = 1, . . . , k. Set S = Sk .
If |W | < |S|, then |W | = |S| − 1 by Theorem 5.2 a). Hence W = S \ {s} for some s ∈ S.
First suppose that s ∈ T . Thus, W = (T \ {s}) ∪ {s1 , . . . , sk }. Since |W | = |Sk−1 |, |W \ Sk−1 | = 1 and
W ∪ Sk−1 = S ∈ M(G), by Lemma 5.5 (ii) it follows that Sk−1 ∩ W = (T \ {s}) ∪ {s1 , . . . , sk−1 } ∈ M(G).
For every i = 1, . . . , k − 2, let Ti = Si+1 ∩ · · · ∩ Sk−1 ∩ W . By induction on i ≤ k − 2, assume that
Ti ∈ M(G), then Ti−1 = Si ∩ Ti = (T \ {s}) ∪ {s1 , . . . , si } ∈ M(G) by Lemma 5.5 (ii), since |Si | = |Ti |,
|Ti \Si | = 1 and Si ∪Ti = Si+1 ∈ M(G). In particular, T0 = S1 ∩· · ·∩Sk−1 ∩W = (T \{s})∪{s1 } ∈ M(G),
|T0 | = |T |, |T0 \ T | = 1 and T0 ∪ T = S1 ∈ M(G). Again, by Lemma 5.5 (ii), T ∩ T0 = T \ {s} ∈ M(G), a
contradiction.
Now assume that s ∈ S \T , where s = sj for some j ∈ {1, . . . , k}. Since |W | = |Sk−1 | and |W \Sk−1 | = 1,
by Lemma 5.5 (ii), Sk−1 ∩W = Sk−1 \{sj } ∈ M(G). For every i = j, . . . , k−2, let Ti = Si+1 ∩· · ·∩Sk−1 ∩W .
By induction on i ≤ k − 2, assume that Ti ∈ M(G), then Ti−1 = Si ∩ Ti = Si \ {sj } ∈ M(G) by Lemma 5.5

24

(ii), since |Si | = |Ti |, |Ti \ Si | = 1 and Si ∪ Ti = Si+1 ∈ M(G). In particular, Tj−1 = Sj ∩ · · · ∩ Sk−1 ∩ W =
Sj \ {sj } = Sj−1 ∈ M(G). Therefore,
P ′ : PS0 = PT , PS1 , . . . , PSj−1 = PTj−1 , PTj , . . . , PTk−2 , PW
is a path from PT to PW , shorter than P, a contradiction.
If |W | = |S|, then W = (S \ {x}) ∪ {y} for some x, y. If x ∈ T , then W = (T \ {x}) ∪ {s1 , . . . , sk , y}.
By Lemma 5.5 (i), W ∩ S = (T \ {x}) ∪ {s1 , . . . , sk } ∈ M(G). We may proceed in a similar way to the
case |W | < |S|, setting Ti = Si+1 ∩ · · · ∩ Sk ∩ W for i = 1, . . . , k − 1.
Now assume x ∈ S \ T , where x = sj for some j ∈ {1, . . . , k}. Since |W | = |S|, by Lemma 5.5 (i),
S ∩W = S \{x} ∈ M(G). Again, we may proceed as in the case |W | < |S|, setting Ti = Si+1 ∩· · ·∩Sk ∩W
for i = j, . . . , k − 1.
In both cases we find a contradiction. In conclusion, we proved that, if there exists a path from PT
to PW in D(G), then |W | > |T | ≥ 2. Thus, there is no path from PT to P∅ in D(G), hence D(G) is
disconnected.

Using the following result, we may reduce to consider bipartite graphs G with exactly two cut vertices
and D(G) connected.
Theorem 5.8. Let G be a bipartite graph with at least three cut vertices and such that JG is unmixed.
a) There exist G1 and G2 such that G = G1 ∗ G2 or G = G1 ◦ G2 .
b) If D(G) is connected, then D(G1 ) and D(G2 ) are connected.
Proof. a) By Proposition 2.3, G has exactly two leaves. Let v be a cut vertex that is not a neighbour
of a leaf and let H1 and H2 be the connected components of G{v} . If v is a leaf of both GV (H1 )∪{v} and
GV (H2 )∪{v} , then G = GV (H1 )∪{v} ∗ GV (H2 )∪{v} .
Assume that v is not a leaf of GV (H1 )∪{v} and of GV (H2 )∪{v} . Then, given two new vertices w1 and w2 ,
for i = 1, 2 we set Gi to be the graph (GV (Hi )∪{v} ) ∪ {v, wi }. It follows that G = G1 ◦ G2 .
Now assume by contradiction that v is a leaf of GV (H2 )∪{v} , but not of GV (H1 )∪{v} , and let w be the
only neighbour of v in GV (H2 )∪{v} . Hence, w is a cut vertex of G and we may assume that it is not a leaf
of GV (H2 ) , otherwise G = GV (H1 )∪{v,w} ∗ GV (H2 ) .
The graphs GV (H1 )∪{v} and GV (H2 ) are bipartite with bipartitions V1 ⊔ V2 and W1 ⊔ W2 , respectively.
Without loss of generality, assume that v ∈ V1 and w ∈ W1 and let S = V1 \ {ℓ : ℓ is a leaf of G}. This
is a cut set of G: indeed in GS all vertices of V2 are either isolated or connected with only one leaf of
G, hence every element of S connects at least one vertex of V2 with some other connected component.
Therefore, since JG is unmixed, GS has |S| + 1 connected components, GV (H2 ) is one of them and the
vertices of GV (H1 ) not in S form the remaining |S| connected components. In the same way, the set
T = W1 \ {ℓ : ℓ is a leaf of G} ∈ M(G) and GT consists of the connected component GV (H1 )∪{v} and of
|T | connected components on the vertices of GV (H2 ) that are not in T . Notice that S ∪ T is a cut set of
G: in fact, adding either v or w to GS∪T , we join at least two connected components, since v is not a leaf
of GV (H1 )∪{v} and w is not a leaf of GV (H2 ) . Then GS∪T has |S| connected components on the vertices of
GV (H1 )∪{v} and |T | on the vertices of GV (H2 ) . Hence, cG (S ∪ T ) = |S| + |T |, a contradiction.
b) We prove the statement for G1 , the argument for G2 is the same. Let PS be the primary components
of JG1 , S0 ∈ M(G1 ) and k = |S0 |. Thus, S0 ∈ M(G) by Theorems 4.2 and 4.5. Moreover, by Theorem 5.7,

25

there exists s1 ∈ S0 such that S1 = S0 \ {s1 } ∈ M(G). Applying repeatedly Theorem 5.7, we find a finite
sequence of cut sets S2 = S0 \ {s1 , s2 }, S3 = S0 \ {s1 , s2 , s3 }, . . . , Sk = S0 \ S0 = ∅ ∈ M(G). Notice that
Si ∈ M(G1 ) for i = 1, . . . , k and, by Theorem 5.2, {PSi , PSi+1 } is an edge of M(G1 ) for i = 1, . . . , k − 1.
Hence,
P : PS0 , PS1 , PS2 , . . . , Pk = P∅ ,
is a path from PS to P∅ in D(G1 ). Therefore, D(G1 ) is connected.



Remark 5.9. If the graph G is not bipartite, Theorem 5.8 a) does not hold. For instance, the ideal JG
of the graph in Figure 17 is unmixed, indeed Cohen-Macaulay, and G has four cut vertices, but it is not
possible to split it using the operations ∗ and ◦.

Figure 17

The remaining part of the section is useful to prove that a bipartite graph G with exactly two cut
vertices and D(G) connected is of the form Fm .
Corollary 5.10. Let G be a bipartite graph such that D(G) is connected. Then every non-empty cut set
S ∈ M(G) contains a cut vertex.
Proof. Let S ∈ M(G) and k = |S|. We may assume k ≥ 2. By Theorem 5.7, there exists s ∈ S such that
T = S \ {s} ∈ M(G). By induction, T contains a cut vertex and the claim follows.

Remark 5.11. All assumptions in Theorem 5.8 and Corollary 5.10 are needed. In fact, both claims do
not hold if we only assume G bipartite but D(G) is not connected. For instance, let G = M3,4 . Then
{3, 5} is a cut set that does not contain any cut vertex (see Example 2.2).
On the other hand, both results do not hold if D(G) is connected but G is not bipartite. For example,
if G is the graph in Figure 12(a), then {3, 4} ∈ M(G), but 3 and 4 are not cut vertices of G.
Corollary 5.12. Let G be a bipartite graph with bipartition V1 ⊔ V2 and with exactly two cut vertices v1
and v2 . If D(G) is connected, then {v1 , v2 } ∈ E(G). In particular |V1 | = |V2 |.
Proof. Let fi be the leaf adjacent to vi for i = 1, 2. Assume that {v1 , v2 } ∈
/ E(G). Then Si = NG (vi ) \ {fi }
is a cut set of G for i = 1, 2. Moreover, S1 and S2 do not contain cut vertices. By Corollary 5.10 it follows
that D(G) is disconnected, a contradiction. The last part of the claim follows from Remark 2.4.

Lemma 5.13. Let G be a bipartite graph with bipartition V1 ⊔ V2 , |V1 | = |V2 | and with exactly two cut
vertices. If D(G) is connected, then there exists a vertex of G with degree 2.
Proof. Suppose by contradiction that all the vertices of G, except the two leaves, have degree greater than
2. Let f be the only leaf of G in V1 and consider T = V1 \ {f }. Clearly GT is the disjoint union of |V2 | − 1
isolated vertices and the edge {v2 , f }, where v2 ∈ V2 is a cut vertex. Therefore, T is a cut set and we
claim that it is an isolated vertex in D(G).

26

Notice that T is not contained in any other cut set. Moreover, suppose that S is a cut set of G such
that S ⊂ T and T \ S = {v}. Since S ⊂ V1 , it follows that degGS (v) > 2. Then cG (S) = cG (T \ {v}) ≤
cG (T ) − 2 = |V1 | − 2, since GT consists of isolated vertices and one edge. This contradicts the unmixedness
of JG .
Finally, let T ′ be a cut set such that T \ T ′ = {v} and T ′ \ T = {v ′ }. If we set S = T \ {v} = T ′ \ {v ′ },
it follows that v ′ has to be a cut vertex of GS . As consequence, v ′ = v2 is the cut vertex in V2 , and
{v, v ′ } ∈ E(G). On the other hand, as before, GS has at most |V2 | − 2 connected components, then
cG (T ′ ) = cG (S) + 1 ≤ |V2 | − 1. This contradicts the unmixedness of JG , because |T ′ | = |V2 | − 1. Therefore,
Theorem 5.2 implies that T is an isolated vertex in D(G) against our assumption.

Proposition 5.14. Let H be a bipartite graph with bipartition V1 ⊔ V2 and |V1 | = |V2 |. Let v and f be two
new vertices and let G be the bipartite graph with V (G) = V (H) ∪ {v, f } and E(G) = E(H) ∪ {{v, x} :
x ∈ V1 ∪ {f }}. If D(G) is connected, then D(H) is connected.
Proof. Let f2 be the leaf of G in V2 and w its only neighbour, which is a cut vertex. Lemmas 2.6 b) and
5.13 imply that there is a vertex with degree 2 in G. Thus, by Proposition 2.8,
M(G) = {∅, V1 } ∪ {S ∪ {v} : S ∈ M(H)} ∪ {T ⊂ V1 : T ∈ M(H)}.
Let us denote by PS the primary components of JG and by QS those of JH . Using Theorem 5.2, we can
give a complete description of the edges of D(G):
{P∅ , PT } ∈ E(D(G)) if and only if either T = {v} or T = {w},
{PV1 , PT } ∈ E(D(G)) if and only if either T = V1 \ {f1 } or T = (V1 \ {f1 }) ∪ {v};
if S1 , S2 ∈ M(H), then {PS1 ∪{v} , PS2 ∪{v} } ∈ E(D(G)) if and only if {QS1 , QS2 } ∈ E(D(H));
if T1 , T2 ∈ M(G) are strictly contained in V1 , then we have {PT1 , PT2 } ∈ E(D(G)) if and only if
{QT1 , QT2 } ∈ E(D(H));
(v) if S, T ∈ M(H) and T ( V1 , then {PS∪{v} , PT } ∈ E(D(G)) if and only if S = T .

(i)
(ii)
(iii)
(iv)

If S ∈ M(H), it is enough to prove that QS is in the same connected component as Q∅ in D(H). By
(iii), this is equivalent to prove that in D(G) there exists a path P{v} = PU1 , PU2 , . . . , PUr = PS∪{v} such
that Ui contains v for all i. Since D(G) is connected, we know that there exists a path P from P{v} to
PS∪{v} . We first note that, if P contains P∅ or PV1 , we may avoid them: in fact, by (i) and (ii), they
only have two neighbours; for PV1 they are adjacent by (v), whereas we may replace P∅ with P{v,w} by
(iii) and (v). Let i be the smallest index for which Ui does not contain v. This means that Ui ( V1 and
Ui−1 = Ui ∪ {v} by (v). Moreover, Ui+1 does not contain v, otherwise it would be equal to Ui−1 (again by
(v)). Therefore, Ui+1 ( V1 and {QUi , QUi+1 } ∈ E(D(H)) by (iv). Thus, replacing Ui with Ui+1 ∪ {v} in
P, we get a new path from P{v} to PS∪{v} , by (iii) and (iv). Repeating the same argument finitely many
times, we eventually find a path from P{v} to PS∪{v} that involves only cut sets containing v. Thus D(H)
is connected by (iii).

6. The main theorem
In this section we prove the main theorem of the paper and give some applications.

27

Theorem 6.1. Let G be a connected bipartite graph. The following properties are equivalent:
a)
b)
c)
d)

JG is Cohen-Macaulay;
the dual graph D(G) is connected;
G = A1 ∗ A2 ∗ · · · ∗ Ak , where Ai = Fm or Ai = Fm1 ◦ · · · ◦ Fmr , for some m ≥ 1 and mj ≥ 3;
JG is unmixed and for every non-empty S ∈ M(G), there exists s ∈ S such that S \ {s} ∈ M(G).

Proof. The implication a) ⇒ b) follows by Hartshorne’s Connectedness Theorem [8, Proposition 1.1,
Corollary 2.4, Remark 2.4.1].
b) ⇒ c): We may assume that G has more than two vertices. Recall that, since D(G) is connected,
then JG is unmixed. By Proposition 2.3, G has exactly two leaves, hence at least two cut vertices v1 , v2 ,
which are their neighbours. We proceed by induction on the number h ≥ 2 of cut vertices of G.
Let h = 2. We claim that G = Fm , for some m ≥ 2. Let V (G) = V1 ⊔ V2 be the bipartition of the vertex
set of G. By Corollary 5.12, we have that {v1 , v2 } ∈ E(G) and |V1 | = |V2 |, with vi ∈ Vi for i = 1, 2. We
proceed by induction on m = |V1 | = |V2 |. If m = 2, then G = F2 . Let m > 2 and consider the graph H
obtained removing v2 and the leaf adjacent to it. Lemma 2.6 b) implies that v has degree m and H has
exactly two cut vertices, whereas by Proposition 5.14, D(H) is connected. Hence, by induction, it follows
that H = Fm−1 and G = Fm by construction.
Assume now h > 2. Let v be a cut vertex of G such that v 6= v1 , v2 . By Theorem 5.8, there exist two
graphs G1 and G2 such that G = G1 ∗G2 or G = G1 ◦G2 and D(G1 ), D(G2 ) are connected. If G = G1 ∗G2 ,
by induction they are of the form A1 ∗ A2 ∗ · · · ∗ Ak , for some k ≥ 1, where Ai = Fm , with m ≥ 1, or
Ai = Fm1 ◦ · · · ◦ Fmr , with mj ≥ 3 for j = 1, . . . , r.
On the other hand, if G = G1 ◦ G2 , it follows that G1 = A1 ∗ A2 ∗ · · · ∗ As and G2 = B1 ∗ B2 ∗ · · · ∗ Bt ,
where each Ai and Bi are equal to Fm , for some m ≥ 1, or to Fm1 ◦ · · · ◦ Fmr , with mj ≥ 3 for j = 1, . . . , r.
By Theorem 4.5, it follows that if As = Fm or B1 = Fm , then m ≥ 3.
c) ⇒ a): Let G be a graph as in c). We proceed by induction on k ≥ 1.
If k = 1, then G = Fm for some m ≥ 1, or G = Fm1 ◦ · · · ◦ Fmr , with mj ≥ 3 for j = 1, . . . , r. In the
first case the claim follows from Proposition 3.3, in the latter from Theorem 4.9.
Let k > 1 and consider the graphs G1 = A1 ∗ A2 ∗ · · · ∗ Ak−1 and G2 = Ak . By induction, JG1 is
Cohen-Macaulay and, by the previous argument, also JG2 is Cohen-Macaulay. Then, the claim follows
from Theorem 4.2.
b) ⇔ d): The first implication follows from Theorem 5.7. Conversely, let S ∈ M(G), S 6= ∅, and PS be
the primary components of JG . It suffices to show that there exists a path from P∅ to PS . If |S| = 1, the
claim follows by Theorem 5.2 b). If |S| > 1, by assumption, there exists s ∈ S such that S \ {s} ∈ M(G)
and, by induction, there exists a path from P∅ to PS\{s} . Thus, Theorem 5.2 b) implies that {PS\{s} , PS }
is an edge of D(G).

Theorem 6.1 can be restated in the following way. Let G be a connected bipartite graph. If it has
exactly two cut vertices, then JG is Cohen-Macaulay if and only if G = Fm for some m ≥ 1. If it has more
than two cut vertices, then JG is Cohen-Macaulay if and only if there exist two bipartite graphs G1 , G2
such that JG1 , JG2 are Cohen-Macaulay and G = G1 ∗ G2 or G = G1 ◦ G2 .
Figure 18 shows a graph G obtained by a sequence of operations ∗ and ◦ on a finite set of graphs of the
form Fm . More precisely, G = F3 ∗ F3 ◦ F4 ∗ F1 ∗ F3 ◦ F3 and vi denotes the only common vertex between
two consecutive blocks. By Theorem 6.1, JG is Cohen-Macaulay.

28

v1

v3

v4

v2

v5

Figure 18. The graph G = F3 ∗ F3 ◦ F4 ∗ F1 ∗ F3 ◦ F3
It is interesting to notice that, Theorem 6.1 gives, at the same time, a classification of other known
classes of Cohen-Macaulay binomial ideals associated with graphs. We recall that, given a graph G, the
Lovász-Saks-Schrijver ideal LG (see [11]), the permanental edge ideal ΠG (see [11, Section 3]) and the
parity binomial edge ideal IG (see [12]) are defined respectively as
LG = (xi xj + yi yj : {i, j} ∈ E(G)),
ΠG = (xi yj + xj yi : {i, j} ∈ E(G)),
IG = (xi xj − yi yj : {i, j} ∈ E(G)).
Corollary 6.2. Let G be a bipartite connected graph. Then Theorem 6.1 holds for LG , ΠG and IG .
Proof. Let G be a bipartite graph with bipartition V (G) = V1 ⊔ V2 . Then the binomial edge ideal JG can
be identified respectively with LG , ΠG and IG by means of the isomorphisms induced by:
(
(
(
(xi , yi )
if i ∈ V1
(xi , yi )
if i ∈ V1
(xi , yi ) if i ∈ V1
LG
ΠG
IG
(xi , yi ) 7−−→
, (xi , yi ) 7−−→
, (xi , yi ) 7−−→
.
(yi , −xi ) if i ∈ V2
(−xi , yi ) if i ∈ V2
(yi , xi ) if i ∈ V2
Notice that the first transformation is more general than the one described in [11, Remark 1.5].
Thus, for bipartite graphs, these four classes of binomial ideals are essentially the same and Theorem
6.1 classifies which of these ideals are Cohen-Macaulay.

As a final application, we show that [2, Conjecture 1.6] holds for Cohen-Macaulay binomial edge ideals
of bipartite graphs. Recall that the diameter, diam(G), of a graph G is the maximal distance between two
of its vertices. A homogeneous ideal I in A = K[x1 , · · · , xn ] is called Hirsch if diam(D(I)) ≤ ht(I). In [2],
the authors conjecture that every Cohen-Macaulay homogeneous ideal generated in degree two is Hirsch.
Corollary 6.3. Let G be a bipartite connected graph such that JG is Cohen-Macaulay. Then JG is Hirsch.
Proof. Let S ∈ M(G) be a cut set of G and let n = |V (G)|. We may assume n ≥ 3, otherwise D(JG ) is
a single vertex. Since JG is unmixed, GS has exactly |S| + 1 connected components and we claim that
|S| ≤ ⌈ n2 ⌉ − 1. In fact, if |S| ≥ ⌈ n2 ⌉, we would have
lnm lnm
n n
+
+ 1 ≥ + + 1 = n + 1,
|V (G)| ≥ |S| + |S| + 1 ≥
2
2
2
2

a contradiction. Consider now another cut set T of G. By Theorem 6.1 d), it follows that there is a
path connecting PS and PT , containing P∅ and with length |S| + |T | ≤ 2(⌈ n2 ⌉ − 1) ≤ n − 1. Thus,
diam(D(JG )) ≤ n − 1 = ht(JG ).


29

Acknowledgments
The authors acknowledge the extensive use of the software Macaulay2 [7] and Nauty [16]. They also
thank Giancarlo Rinaldo for pointing out an error in Remark 3.1 in a previous version of the manuscript.
References
[1] A. Banerjee, L. Núñez-Betancourt, Graph connectivity and binomial edge ideals, Proc. Amer. Math. Soc. 145
(2017), 487-499.
[2] B. Benedetti, M. Varbaro, On the dual graph of Cohen-Macaulay algebras, Int. Math. Res. Not. 17 (2015), 8085-8115.
[3] W. Bruns, U. Vetter, Determinantal Rings, Lecture Notes in Mathematics (2nd ed.), Vol. 1327 (1988), Springer,
Heidelberg.
[4] R. Diestel, Graph Theory, Graduate Texts in Mathematics (4th ed.), Vol. 173 (2010), Springer-Verlag, Heidelberg.
[5] V. Ene, J. Herzog, T. Hibi, Cohen-Macaulay binomial edge ideals, Nagoya Math. J. 204 (2011), 57-68.
[6] V. Ene, J. Herzog, T. Hibi, Koszul binomial edge ideals, in “Bridging Algebra, Geometry, and Topology”, Springer
Proc. Math. Stat. 96, Springer, Cham, (2014), 125-136.
[7] D. R. Grayson, M. E. Stillman, Macaulay2, a software system for research in Algebraic Geometry, available at
http://www.math.uiuc.edu/Macaulay2/.
[8] R. Hartshorne, Complete intersections and connectedness, Amer. J. Math. 84 (1962), 497-508.
[9] J. Herzog, T. Hibi, Distributive lattices, bipartite graphs and Alexander duality, J. Algebr. Comb. 22 (2005), 289-302.
[10] J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle, J. Rauh, Binomial edge ideals and conditional independence
statements, Adv. Appl. Math. 45 (2010), 317-333.
[11] J. Herzog, A. Macchia, S. Saeedi Madani, V. Welker, On the ideal of orthogonal representations of a graph in
R2 , Adv. Appl. Math. 71 (2015), 146-173.
[12] T. Kahle, C. Sarmiento, T. Windisch, Parity binomial edge ideals, J. Algebr. Comb. 44 (2016), 1, 99-117.
[13] D. Kiani, S. Saeedi Madani, Some Cohen-Macaulay and unmixed binomial edge ideals, Comm. Alg. 43 (2015), 12,
5434-5453.
[14] D. Kiani, S. Saeedi Madani, The Castelnuovo-Mumford regularity of binomial edge ideals, J. Combin. Theory Ser. A
139 (2016), 80-86.
[15] M. Matsuda, S. Murai, Regularity bounds for binomial edge ideals, J. Commut. Alg. 5 (2013), 1, 141-149.
[16] B. D. McKay, A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Computation 60 (2013), 94-112. The
software package Nauty is available at http://cs.anu.edu.au/∼bdm/nauty/.
[17] M. Ohtani, Graphs and ideals generated by some 2-minors, Comm. Algebra 39 (2011), 3, 905-917.
[18] A. Rauf, G. Rinaldo, Construction of Cohen-Macaulay binomial edge ideals, Comm. Algebra 42 (2014), 1, 238-252.
[19] G. Rinaldo, Cohen-Macaulay binomial edge ideals of small deviation, Bull. Math. Soc. Sci. Math. Roumanie 56 (104)
(2013), 4, 497-503.
[20] W. V. Vasconcelos, Arithmetic of Blowup Algebras, London Math. Soc., Lecture Note Series 195, Cambridge University Press, Cambridge, 1994.

Davide Bolognini, Institut für Mathematik, Albrechtstrasse 28a, 49076 Osnabrück, Germany
E-mail address: davide.bolognini@yahoo.it
Antonio Macchia, Dipartimento di Matematica, Università degli Studi di Bari “Aldo Moro”, Via
Orabona 4, 70125 Bari, Italy
E-mail address: macchia.antonello@gmail.com
Francesco Strazzanti, Departamento de Álgebra, Facultad de Matemáticas, Universidad de
Sevilla, Avda. Reina Mercedes s/n, 41080 Sevilla, Spain
E-mail address: francesco.strazzanti@gmail.com

