Cohen-Macaulayness of powers of edge ideals of edge-weighted graphs Thanks: ∗ Corresponding author Thanks: 2020 Mathematics Subject Classification . Primary 13C15, 13C14; Secondary 05E40, 13F20 Thanks: Keywords: Cohen-Macaulayness, powers of the edge ideal, the edge-weighted graph, very well-covered graph, weighted tree Jiaxin Li, Tran Nam Trung, Guangjun Zhu ∗ Abstract . In this paper, we characterize the Cohen-Macaulayness of the second power I ( G ω ) 2 I(G_{\omega})^{2} of the weighted edge ideal I ( G ω ) I(G_{\omega}) when the underlying graph G G is a very well-covered graph. We also characterize the Cohen-Macaulayness of all ordinary powers of I ( G ω ) n I(G_{\omega})^{n} when G G is a tree with a perfect matching consisting of pendant edges and the induced subgraph G [ V ( G ) ∖ S ] G[V(G)\setminus S] of G G on V ( G ) ∖ S V(G)\setminus S is a star, where S S is the set of all leaf vertices, or if G G is a connected graph with a perfect matching consisting of pendant edges and the induced subgraph G [ V ( G ) ∖ S ] G[V(G)\setminus S] of G G on V ( G ) ∖ S V(G)\setminus S is a complete graph and the weight function ω \omega satisfies ω ( e ) = 1 \omega(e)=1 for all e ∈ E ( G [ V ( G ) ∖ S ] ) e\in E(G[V(G)\setminus S]) . 1. Introduction Let G be a finite simple graph with the vertex set V(G) and the edge set E(G) . A subset X of V(G) is said to be independent if there is no edge xy\in E(G) for x,y\in X . If X is an independent set and maximal in terms of inclusion, then X is called the maximal independent set of G , and its cardinality is called the independence number of G . A graph G is called well-covered (also called unmixed ) if all maximal independent sets of G have the same independence number. It is known that a well-covered graph is a member of the class W_{2} if removing any vertex leaves a well-covered graph with the same independence number as itself (see [ 18 ] ). A graph G without isolated vertices is said to be very well-covered if |V(G)| is an even integer and every maximal independent set of G has cardinality |V(G)|/2 . A function \omega\colon E(G)\to\mathbb{Z}_{>0} is called an edge-weighted function (weighted function for short) on E(G) . The pair (G,\omega) is called a weighted graph and is denoted by G_{\omega} . If V(G)=\{x_{1},\ldots,x_{d}\} , then we can assume that R=K[x_{1},\ldots,x_{d}] is a polynomial ring over a field K . The weighted edge ideal of G_{\omega} is defined as a monomial ideal of R as follows: I(G_{\omega})=((x_{i}x_{j})^{\omega(x_{i}x_{j})}\mid x_{i}x_{j}\in E(G)). If the weighted function \omega on E(G) is the trivial one, i.e. \omega(e)=1 for all e\in E(G) , then I(G_{\omega}) is just the classical edge ideal of G , denoted by I(G) . It is known (see e.g. [ 24 , Proposition 6.1.16] ) that \ass(R/I(G))=\{(v:v\in C)\mid C\text{ is a minimal vertex cover of }G\}. In particular, \dim R/I(G)=\alpha(G) , where \alpha(G) is the maximum cardinality of independent sets in G . For an ideal I\subset R , we say that it is Cohen-Macaulay (resp. Gorenstein) if the quotient ring R/I is Cohen-Macaulay (resp. Gorenstein). A graph G is called a Cohen-Macaulay (resp. Gorenstein) graph if its edge ideal I(G) is Cohen-Macaulay (resp. Gorenstein). It is known that if G is Gorenstein, then it is Cohen-Macaulay, so it is also well-covered. Note that I(G)=\sqrt{I(G_{\omega})} , so G is Cohen-Macaulay if G_{\omega} is Cohen-Macaulay (due to [ 10 , Theorem 2.6] ). Recall that for a homogeneous ideal I\subset R and any integer n\geq 1 , the n -th symbolic power of I is defined as I^{(n)}=\bigcap\limits_{\mathfrak{p}\in\Min(I)}I^{n}R_{\mathfrak{p}}\cap R, where \Min(I) is the set of minimal primes of I . Much research has been done on the characterization of Cohen-Macaulay graphs. Examples include bipartite graphs, chordal graphs, toric graphs, large perimeter graphs, etc. ( see [ 8 , 9 , 12 , 14 , 21 , 22 , 23 ] ) . For the higher powers and higher symbolic power of I(G) , Hoang and the second author of this paper proved in [ 14 ] that I(G)^{2} is Cohen-Macaulay if and only if G is a triangle-free Gorenstein graph. Furthermore, Cowsik and Nori in [ 1 ] showed that for a homogeneous radical ideal I\subset R , I^{n} is Cohen-Macaulay for infinitely many n if and only if I is a complete intersection. In particular, I(G)^{n} is Cohen-Macaulay for infinitely many n if and only if I(G) is a complete intersection. Hoang, Minh and the second author of this paper proved in [ 13 ] that I(G)^{(2)} is Cohen-Macaulay if and only if G is a Cohen-Macaulay graph and for all edges xy , G_{xy} is Cohen-Macaulay and \alpha(G_{xy})=\alpha(G)-1 , where G_{xy}=G\setminus(N(x)\cup N(y)) is the localization of G at the edge xy . In [ 5 ] , Giancarlo, Naoki and Ken-ichi showed that I(G)^{(n)} is Cohen-Macaulay for some integer n\geq 3 if and only if G is a disjoint union of finitely many complete graphs. In this case, I(G)^{(n)} is Cohen-Macaulay for all n . We know that if I(G)^{n} is Cohen-Macaulay, then I(G)^{n}=I(G)^{(n)} . Recently, there has been a surge of interest in characterizing weight functions for which the edge ideal of a weighted graph is Cohen-Macaulay, and in computing the depth of powers of the edge ideals of some weighted graphs. For example, Paulsen and Sather-Wagstaff in [ 16 ] classified Cohen-Macaulay weighted graphs G_{\omega} where the underlying graph G is a cycle, a tree, or a complete graph. Seyed Fakhari et al. in [ 19 ] continued this study, they classified Cohen-Macaulay weighted graph G_{\omega} when G is a very well-covered graph. Recently, Diem et al. in [ 3 ] gave a complete characterization of sequentially Cohen-Macaulay weighted graphs. In [ 25 ] , Wei classified all Cohen-Macaulay weighted chordal graphs from a purely graph-theoretic point of view. Hien in [ 11 ] classified Cohen-Macaulay weighted graphs G_{\omega} if G has a girth of at least 5 . In [ 26 ] , Zhu et al. gave some exact formulas for the depth of the powers of the edge ideal of a weighted star graph and also gave some lower bounds on the depth of powers of the integrally closed weighted path. In this paper, we will focus on characterize the Cohen-Macaulayness of the second power I(G_{\omega})^{2} of the weighted edge ideal I(G_{\omega}) when the underlying graph G is a very well-covered graph. We also characterize the Cohen-Macaulayness of all ordinary powers of I(G_{\omega})^{n} when G is a tree with a perfect matching consisting of pendant edges and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a star, where S is the set of all leaf vertices, or if G is a connected graph with a perfect matching consisting of pendant edges and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a complete graph and the weight function \omega satisfies \omega(e)=1 for all e\in E(G[V(G)\setminus S]) . The article is organized as follows. In Section 2 , we will collect some of the essential definitions and terminology that will be needed later. In Section 3 , we will prove that if G is a Cohen-Macaulay very well-covered graph, then G has at least two leaves. Furthermore, if G has exactly two leaves, then it is bipartite. We also give the necessary and sufficient condition that I(G_{\omega})^{2} is Cohen-Macaulay using the weight function \omega . In Section 4 , if G is a path of length of 3 , using the weight function \omega , we give the necessary and sufficient condition that I(G_{\omega})^{n} is Cohen-Macaulay for all n\geq 1 (see Proposition 4.3 ). Under the condition that G is a tree, we give the conditions that the weight function \omega satisfies if I(G_{\omega})^{n} is Cohen-Macaulay for all n\geq 1 . Furthermore, if G is a tree with a perfect matching consisting of pendant edges and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a star, where S is the set of all leaf vertices, we show that these conditions are crucial. If G is a connected graph with a perfect matching consisting of pendant edges, and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a complete graph, and the weight function \omega satisfies \omega(e)=1 for all e\in E(G[V(G)\setminus S]) , we show that I(G_{\omega})^{n} is Cohen-Macaulay for all n\geq 1 if and only if \omega(e)\geqslant 2 for any pendant edge e . 2. Preliminaries We begin this section by collecting some terminology and results from graph theory. Let G be a finite simple graph with a vertex set V(G) and an edge set E(G) . A subset C\subseteq V(G) is a vertex cover of G if, for each e\in E(G) , e\cap C\neq\emptyset . If C is minimal with respect to inclusion, then C is called a minimal vertex cover of G . Obviously, C is a vertex cover if and only if V(G)\setminus C is an independent set. If v is a vertex in G , its neighborhood is the set N_{G}(v)=\{u\in V(G)\mid vu\in E(G)\} and its degree, denoted by \deg_{G}(v) , is |N_{G}(v)| . If \deg_{G}(v)=1 , then v is called a leaf vertex. An edge that is incident with a leaf vertex is called a pendant edge. The closed neighborhood of v is N_{G}[v]=N_{G}(v)\cup\{v\} ; if there is no ambiguity on G , we use N(v) and N[v] , respectively. For an independent set S of G , we denote the closed neighborhood of S by N_{G}[S]=S\cup\{v\in V(G)\mid N_{G}(v)\cap S\neq\emptyset\} ; we write N_{G}[v_{1},\ldots,v_{s}] stands for N_{G}[S] if S=\{v_{1},\ldots,v_{s}\} . A subset M\subset E(G) is a matching if e\cap e^{\prime}=\emptyset for every pair of edges e,e^{\prime}\in M . If every vertex of G is incident with an edge in M , then M is a perfect matching of G . For a subset A\subset V(G) , let G[A] denote the induced subgraph of G on A . At the same time, we denote the induced subgraph of G on V(G)\setminus A by G\setminus A . If A=\{v\} , we will write G\setminus v instead of G\setminus\{v\} for simplicity. Let G_{\omega} be a weighted graph, its induced subgraph is a weighted graph H_{\omega} , where V(H)\subset V(G) , and for any u,v\in V(H) , uv\in E(H) if and only if uv\in E(G) , and the weight \omega_{H}(uv) of edge uv in H is equal to its weight \omega_{G}(uv) in G . A monomial ideal I is unmixed if its associated primes have the same height. It is well known that I is unmixed if R/I is Cohen-Macaulay. If I(G_{\omega}) is unmixed, we say that G_{\omega} is unmixed. Note that I(G)=\sqrt{I(G_{\omega})} , so G is well-covered if G_{\omega} is unmixed. Note also that the height I(G_{\omega}) is equal to the smallest size of the vertex covers of G . Next, we recall a formula by Hochster to ompute the depth of R/I , where I is a monomial ideal. Actually, it gives us a way to check the Cohen-Macaulayness of monomial ideals. Lemma 2.1 . [ 15 , Theorem 7.1] Let I be a monomial ideal. Then \depth R/I=\min\{\depth R/\sqrt{I\colon f}\mid f\text{ is a monomial such that }f\notin I\}. As a consequence, we obtain Lemma 2.2 . Let I be a monomial ideal. Then I is Cohen-Macaulay if and only if I has no embedded prime ideal and I\colon f is Cohen-Macaulay for every monomial f\notin I . Let V be the set of all variables of R . For a monomial f in R , its support is \supp(f)=\{x\in V\mid x\text{ is divisible by }f\} , i.e., it is the set of all variables appearing in f . For a monomial ideal I of R and a subset W of V , the restriction of I on W is I|_{W}=(f\mid f\text{ is a minimal generator of\ }I\text{ such that }\supp(f)\subseteq W), denoted by I|_{W} , and define I_{W}=IR_{W}\cap R as the localization of I with respect to W . Note that I_{W}=I\colon f^{\infty} with f=\prod_{x\in W}x . The following lemmas are obvious. Lemma 2.3 . Let I and J be two monomial ideals in R and let W be a subset of V . Then (1) (I\cap J)|_{W}=I|_{W}\cap J|_{W} ; and (2) (I^{n})|_{W}=(I|_{W})^{n} for all n\geqslant 1 . Lemma 2.4 . Let I and J be two monomial ideals in R and let W\subseteq V . Then (1) (I\cap J)_{W}=I_{W}\cap J_{W} ; (2) (I^{n})_{W}=(I_{W})^{n} for all n\geqslant 1 ; and (3) if I is Cohen-Macaulay, then I_{W} is also Cohen-Macaulay. Lemma 2.5 . Suppose that G has a pendant edge xy with \deg_{G}(y)=1 . For any integer n\geq 1 , if I(G_{\omega})^{n} is unmixed, then I((G\setminus x)_{\omega})^{n} is also unmixed. Proof. For simplicity, set I=I(G_{\omega}) and H=G\setminus x . Assume that I=Q_{1}\cap Q_{2}\cap\cdots\cap Q_{k}\cap Q_{k+1}\cap\cdots\cap Q_{m}\cap Q_{m+1}\cap\cdots\cap Q_{s} is an irredundant primary decomposition of I , where • \hgt(Q_{i})=\hgt(I) for i=1,\ldots,m ; and \hgt(Q_{i})>\hgt(I) for i=m+1,\ldots,s . • x\in Q_{i} for i=1,\ldots,k ; and y\in Q_{i} for i=k+1,\ldots,m . Since I^{n} is unmixed, we have I^{n}=I^{(n)} , where I^{(n)} is the n -th symbolic power of I . So I^{n}=Q_{1}^{n}\cap\cdots\cap Q_{k}^{n}\cap Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n} . Let I^{\prime} be the restriction of I on V(G)\setminus\{x\} , then, by Lemma 2.3 , we have I(H_{\omega})^{n}=(I^{\prime})^{n}=(I^{n})^{\prime} . So again by this lemma we get that I(H_{\omega})^{n}={Q^{\prime}}_{1}^{n}\cap\cdots\ {Q^{\prime}}_{k}^{n}\cap Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n} is a primary decomposition of I(H_{\omega})^{n} . Since every monomial generator of I(H_{\omega})^{n} contains neither x nor y , it follows that I(H_{\omega})^{n}={Q^{\prime}}_{1}^{n}\cap\cdots\cap{Q^{\prime}}_{k}^{n}. Since every {Q^{\prime}}_{i} with i=1,\ldots,k has height \hgt(I)-1 , this representation is an irredundant primary decomposition of I(H_{\omega})^{n} , and thus I(H_{\omega})^{n} is unmixed, as required. ∎ Further, we obtain Lemma 2.6 . Suppose that G has a pendant edge xy with \deg_{G}(y)=1 . For any integer n\geq 1 , if I(G_{\omega})^{n} is Cohen-Macaulay, then I((G\setminus x)_{\omega})^{n} is Cohen-Macaulay. Proof. Let I=I(G_{\omega}) , H=G\setminus x and I=Q_{1}\cap\cdots\cap Q_{k}\cap Q_{k+1}\cap\cdots\cap Q_{m}\cap Q_{m+1}\cap\cdots\cap Q_{s} be an irredundant primary decomposition of I such that • \hgt(Q_{i})=\hgt(I) for i=1,\ldots,m ; and \hgt(Q_{i})>\hgt(I) for i=m+1,\ldots,s . • x\in Q_{i} for i=1,\ldots,k ; and y\in Q_{i} for i=k+1,\ldots,m . Since I^{n} is Cohen-Macaulay, it is unmixed. Hence I^{n}=Q_{1}^{n}\cap\cdots\cap Q_{k}^{n}\cap Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n} by Lemma 2.5 . Let I^{\prime} be the restriction of I on V(G)\setminus\{x\} , then, by the proof of Lemma 2.5 , we get that I(H_{\omega})^{n}={Q^{\prime}}_{1}^{n}\cap\cdots\cap{Q^{\prime}}_{k}^{n} is an irredundant primary decomposition of I(H_{\omega})^{n} . Let P_{i}=\sqrt{Q_{i}} and P^{\prime}_{i}=\sqrt{Q^{\prime}_{i}} for i=1,\ldots,k . Let f be any monomial with \supp(f)\subseteq V(G)\setminus\{x,y\} such that f\notin I(H_{\omega})^{n} . Suppose f\notin{Q^{\prime}}_{i}^{n} for i=1,\ldots,t and f\in{Q^{\prime}}_{i}^{n} for i=t+1,\ldots,k . In particular, \sqrt{I(H_{\omega})^{n}\colon f}=\sqrt{{Q^{\prime}}_{1}^{n}\colon f}\cap\cdots\cap\sqrt{{Q^{\prime}}_{t}^{n}\colon f}={P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t}. Let g=fy^{n\omega(xy)} , then g\notin Q_{i}^{n} for i=1,\ldots,t ; and g\in Q_{i}^{n} for i=t+1,\ldots,m . It follows that I(G_{\omega})^{n}:g=(Q_{1}^{n}\colon g)\cap\cdots\cap(Q_{t}^{n}\colon g), and so \sqrt{I(G_{\omega})^{n}:g}=\sqrt{{Q}_{1}^{n}\colon g}\cap\cdots\cap\sqrt{{Q}_{t}^{n}\colon g}={P}_{1}\cap\cdots\cap{P}_{t}=(x)+{P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t}. Since I(G_{\omega})^{n}:g is Cohen-Macaulay by Lemma 2.2 , so is (x)+{P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t} . Therefore, \sqrt{I(H_{\omega})^{n}:f}={P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t} is Cohen-Macaulay. It follows that I(H_{\omega})^{n} is Cohen-Macaulay again by Lemma 2.2 , as required. ∎ For a monomial u and a variable x , we denote \deg_{x}(u)=\max\{m:x^{m}|u\} . Lemma 2.7 . Suppose that I(G_{\omega})^{n} is unmixed for some n\geqslant 1 . If G has a pendant edge xy with \deg_{G}(y)=1 , then \omega(xy)\geqslant\omega(xz) for all z\in N_{G}(x) . Proof. Let I=I(G_{\omega}) and let I=Q_{1}\cap\cdots\cap Q_{k}\cap Q_{k+1}\cap\cdots\cap Q_{m}\cap Q_{m+1}\cap\cdots\cap Q_{s} be an irredundant primary decomposition of I , where \hgt(Q_{i})=\hgt(I) for i=1,\ldots,m ; and \hgt(Q_{i})>\hgt(I) for i=m+1,\ldots,s . Since I^{n} is unmixed, we have I^{n}=Q_{1}^{n}\cap\cdots\cap Q_{m}^{n}. Let P_{i}=\sqrt{Q_{i}} for i=1,\ldots,m , where x\in P_{i} for i=1,\ldots,k , and x\notin P_{i} for i=k+1,\ldots,m . Since \ass(R/I^{n})=\{P_{1},\ldots,P_{m}\} , it follows that \ass(R/I^{n})=\ass(R/I(G)) . Since xy is a pendant edge of G , every associated prime ideal of G contains either x or y , but not both. Thus, y\notin P_{i} for i=1,\ldots,k , and y\in P_{i} for i=k+1,\ldots,m . For a monomial ideal J of R , let \G(J) be the set of its minimal monomial generators. We have I^{n}=(Q_{1}^{n}\cap\cdots\cap Q_{k}^{n})\cap(Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n})=((x^{p})+J_{1})\cap((y^{q})+J_{2}) where each monomial f\in\G(J_{1}) has \deg_{x}(f)
\omega_{kt}
by Eq. (
4
). Together with the fact that
f\in J^{2}
, this implies that either
x_{1}^{\omega_{11}}(x_{1}y_{t})^{\omega_{1t}}\mid f
or
(x_{1}y_{t})^{2\omega_{1t}}\mid f
. The first case is impossible because
\deg_{x_{1}}(x_{1}^{\omega_{11}}(x_{1}y_{t})^{\omega_{1t}})>\deg_{x_{1}}(f)
. Hence
(x_{1}y_{t})^{2\omega_{1t}}\mid f
. It follows that
2\omega_{1t}\leqslant\omega_{11}
and
2\omega_{1t}\leqslant\omega_{kt}
.
Similarly, if we choose
g=x_{1}^{\omega_{1k}}y_{t}^{\omega_{tt}}
, then we can get
2\omega_{1t}\leqslant\omega_{tt}
and
2\omega_{1t}\leqslant\omega_{1k}
. The proof is now complete.
∎
Lemma 3.7
.
If
I(G_{\omega})^{2}
is Cohen-Macaulay, then
(1)
2\omega(x_{i}x_{j})\leqslant\min\{\omega(x_{i}y_{i}),\omega(x_{j}y_{j})\}
if
x_{i}x_{j}\in E(G)
with
i\neq j
.
(2)
2\omega(x_{i}x_{j})\leqslant\min\{\omega(x_{i}y_{k}),\omega(x_{k}x_{j})\}
for all different indices
i,j,k
such that
x_{i}y_{k}
,
x_{k}x_{j}\in E(G)
.
Proof.
(1)
We prove the ststement by induction on
t\geqslant 2
. If
t=2
, then it follows from Lemma
3.4
.
Suppose
t\geqslant 3
. Note that
i\neq j
. If
G
has a pendant edge
x_{p}y_{p}
with
p\notin\{i,j\}
, then
I((G\setminus\{x_{p},y_{p}\})_{\omega})^{2}
is Cohen-Macaulay by Lemma
2.6
. By applying the induction hypothesis on
H_{\omega}
, we obtain the desired inequalities. Therefore, we can assume that
x_{p}y_{p}
is not a pendant edge for
p\notin\{i,j\}
, and hence
x_{i}y_{i}
and
x_{j}y_{j}
are the only pendant edges by Lemma
3.2
. In particular,
y_{i}
and
y_{j}
are the only leaves of
G
.
Therefore, by Lemma
3.3
,
G
is bipartite. Thus, by
[
8
, Theorem
3.4
]
,
G
has a bipartition
(U,V)
that satisfies the condition
(*)
. Furthermore, if
U=\{u_{1},\ldots,u_{t}\}
and
V=\{v_{1},\ldots,v_{t}\}
, by
[
2
, Theorem 0.2]
,
G
has a unique perfect matching, we have
\{x_{1}y_{1},\ldots,x_{t}y_{t}\}=\{u_{1}v_{1},\ldots,u_{t}v_{t}\}.
Since
u_{1}v_{1}
and
u_{t}v_{t}
are pendent edges, it follows that
\{x_{i}y_{i},x_{j}y_{j}\}=\{u_{1}v_{1},u_{t}v_{t}\}
. We can assume that
x_{i}y_{i}=u_{1}v_{1}
as edges of
G
so that
x_{j}y_{j}=u_{t}v_{t}
. Since
v_{1},u_{t}
are leaves, we deduce that
y_{i}=v_{1}
and
y_{j}=u_{t}
. Then, the inequality now becomes
2\omega(u_{1}v_{t})\leqslant\min\{\omega(u_{1}v_{1}),\omega(u_{t}v_{t})\}
, which follows from Lemma
3.6
.
(2)
The proof is almost the same as in the previous case. We prove by induction on
t\geqslant 3
. If
t=3
, since
x_{k}y_{k}
is not a pendent edge, we deduce that
G
is a bipartite graph by Lemma
3.3
. Actually, we can check that
(\{x_{i},x_{k},y_{j}\},\{y_{i},y_{k},x_{j}\})
is a bipartition of
G
and it has a representation as in Figure
4
. With this configuration of
G
, the desired inequality follows from Lemma
3.6
.
Figure 4.
The graph
G_{\omega}
after swapping the endpoints of
x_{j}y_{j}
.
Suppose that
t\geqslant 4
. If
G
has a pendant edge
x_{p}y_{p}
with
p\notin\{i,j\}
, then
I((G\setminus\{x_{p},y_{p}\})_{\omega})^{2}
is Cohen-Macaulay by Lemma
2.6
. Applying the induction hypothesis to
H_{\omega}
, we obtain the desired inequalities. Hence we can assume that
x_{p}y_{p}
is not a pendant edge for
p\notin\{i,j\}
, and hence
x_{i}y_{i}
and
x_{j}y_{j}
are the only pendant edges of
G
by Lemma
3.2
. In particular,
y_{i}
and
y_{j}
are the only leaves of
G
. In this case,
G
is bipartite by Lemma
3.3
.
By the same argument as in the previous case,
G
has a bipartition
(U,V)
that satisfies the condition
(*)
, and if
U=\{u_{1},\ldots,u_{t}\}
and
V=\{v_{1},\ldots,v_{t}\}
, then
\{x_{1}y_{1},\ldots,x_{t}y_{t}\}=\{u_{1}v_{1},\ldots,u_{t}v_{t}\}.
Since
u_{1}v_{1}
and
u_{t}v_{t}
are pendent edges of
G
, it follows that
\{x_{i}y_{i},x_{j}y_{j}\}=\{u_{1}v_{1},u_{t}v_{t}\}
. So either
x_{i}y_{i}=u_{1}v_{1}
and
x_{j}y_{j}=u_{t}v_{t}
or
x_{i}y_{i}=u_{t}v_{t}
and
x_{j}y_{j}=u_{1}v_{1}
. This also implies that
x_{k}y_{k}=u_{s}v_{s}
for some
s
with
1t
. There exists some
\ell
such that
\deg_{G}(y_{\ell})>1
. We can construct a new very well-covered graph
G^{\prime}
from
G
such that
V(G^{\prime})=V(G)
and the edge set is
E(G^{\prime})=\{E(G)\setminus\{x_{i}y_{\ell}\mid x_{i}y_{\ell}\in E(G)\text{ with }i<\ell\}\}\cup\{x_{i}x_{\ell}\mid x_{i}y_{\ell}\in E(G)\text{ with }i<\ell\}.
We can check that
G^{\prime}
satisfies the condition
(*)
, so it is also very well-covered.
Next, we define the weight function
\omega^{\prime}
on
E(G^{\prime})
by
\omega^{\prime}(e)=\begin{cases}\omega(x_{i}y_{\ell})&\text{ if }e=x_{i}x_{\ell}\text{ and }x_{i}y_{\ell}\in E(G)\text{ with }i<\ell,\\
\omega(e)&\text{ otherwise}.\end{cases}
We can check that the weight function
\omega^{\prime}
on
E(G^{\prime})
satisfies all the conditions of our theorem and that
m(G^{\prime}_{\omega^{\prime}})