######  Claim 1.

# On Graph Odd Edge-Colorings and Odd Edge-Coverings

Xiao-Chuan Liu  Departamento de Matemática, Universidade Federal de
Pernambuco, Avenida Jornalista Aníbal Fernandes - Cidade Universitária,
Recife, Brasil<EMAIL_ADDRESS>and  Xu Yang  Instituto de Computação,
Universidade Federal de Alagoas, Av. Lourival Melo Mota, S/N, Maceió, Brasil
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we fully resolve two major conjectures on odd edge-colorings
and odd edge-coverings of graphs, proposed by Petruševski and Škrekovski
(European Journal of Combinatorics, 91:103225, 2021). The first conjecture
states that for any loopless and connected graph $G$ with
$\chi_{\text{odd}}^{\prime}(G)=4$, there exists an edge $e$ such that
$G\backslash\\{e\\}$ is odd $3$-edge-colorable. The second conjecture states
that any simple graph $G$ with $\chi_{\text{odd}}^{\prime}(G)=4$ admits an odd
$3$-edge-covering in which only one edge receives two or three colors. In
addition, we strongly confirm the second conjecture by demonstrating that
there exists an odd $3$-edge-covering in which only one edge receives two
colors.

##  1\. Introduction

In this paper, we consider only undirected and loopless graphs, which may
contain multiple edges unless specified otherwise as simple graphs. Throughout
this paper, we employ the graph notation specified in [3].

For a graph $G$, an edge-coloring of $G$ is an assignment of colors from the
set $[k]=\\{1,2,\cdots,k\\}$ to the edges of $G$, which provides an edge
decomposition of $G$ into $k$ color classes. Similarly, an edge-covering of
$G$ is an assignment of colors from $[k]$ to the edges of $G$, allowing for
multiple colors per edge. Equivalently, we can denote an edge-coloring by a
mapping $\varphi:E(G)\to[k]$. In the case of an edge-covering, we denote it by
a set-valued mapping $\psi:E(G)\to 2^{[k]}\backslash\emptyset$. We will
frequently talk about vertices with odd degrees or even degrees. For
simplicity, we call these vertices odd vertices and even vertices,
respectively. A graph is called an odd graph if every vertex is an odd vertex.
We say $G$ is odd $k$-edge-colorable (respectively, odd $k$-edge-coverable) if
there is an edge-coloring (respectively, an edge-covering) of $G$ by $k$ odd
subgraphs, which we call an odd $k$-edge-coloring (respectively, an odd
$k$-edge-covering). In other words, the coloring map or the covering map
$\varphi$ is required to satisfy that for any $j=1,\cdots,k$, the edge set
$E_{j}:=\\{e\in E(G)\big{|}j\in\varphi(e)\\}$ forms an odd graph. We also
define $\chi_{\text{odd}}^{\prime}(G)$ (respectively,
$\text{cov}_{\text{odd}}(G)$) to be the least integer $k_{0}$ such that $G$ is
odd $k_{0}$-colorable (respectively, odd $k_{0}$-coverable). It is reasonable
to call $\chi_{\text{odd}}^{\prime}(G)$ the odd chromatic index of the graph
$G$. Alternatively, we understand $\chi_{\text{odd}}^{\prime}(G)$ as the least
integer $k_{0}$ such that $G$ can be decomposed into $k_{0}$ (edge) disjoint
odd subgraphs.

The topics of determining both $\chi_{\text{odd}}^{\prime}(G)$ and
$\text{cov}_{\text{odd}}(G)$ for a graph $G$ have been very active in recent
years, and we refer to the recent survey paper [6] for the history,
references, and discussions on many related problems, ranging from theoretical
problems on graphs and multigraphs to problems involving algorithms.

As an initiating result in this area, Pyber [8] proved the following theorem.

######  Theorem 1.1.

([8]) For any connected simple graph $G$, $\chi_{\text{odd}}^{\prime}(G)\leq
4$. If $G$ is a connected graph (not necessarily a simple graph) and it has
even order, then $\chi_{\text{odd}}^{\prime}(G)\leq 3$.

It was also observed in [8] that the upper bound of $4$ in the previous result
can be achieved by the wheel graph $W_{4}$. Lužar, Petruševski, and Škrekovski
[1] showed that connected loopless multigraphs are odd 5-edge-colorable, with
one particular exception that is odd 6-edge-colorable. Before proceeding, we
define a Shannon triangle of type $(2,2,2)$ as one of the graphs on three
pairwise adjacent vertices, $v_{1},v_{2},v_{3}$, where any two of them are
connected by multiple edges with even sizes. Similarly, we define a Shannon
triangle of type $(2,2,1)$ for any graph on three pairwise adjacent vertices
$v_{1},v_{2},v_{3}$, where both edge sets between the pairs $v_{1}v_{2}$ and
$v_{1}v_{3}$ have even sizes, and the edge set between $v_{2}v_{3}$ has an odd
size. It can be verified that if $S_{2,2,2}$ is a Shannon triangle of type
$(2,2,2)$, then $\chi_{\text{odd}}^{\prime}(S_{2,2,2})=6$, and if $S_{2,2,1}$
is a Shannon triangle of type $(2,2,1)$, then
$\chi_{\text{odd}}^{\prime}(S_{2,2,1})=5$. In 2017, Petruševski [4] proved
that the above two families of graphs are the only exceptions; all other
graphs are odd $4$-edge-colorable. Furthermore, Petruševski [4] also proved
that when $\chi_{\text{odd}}^{\prime}(G)=4$, a color class can be reduced to a
size of at most 2. In the end of the paper, the author raised a natural
question regarding the existence of an edge-analogue of the second part of
Theorem 1.1. That is, for a graph that is odd $4$-edge-colorable, is it
possible to delete a particular edge (instead of a vertex), such that the
resulting graph is odd $3$-edge-colorable? Additionally, the following
conjecture was formally raised later in [6].

######  Conjecture 1.2.

(Conjecture 2.14 of [6]) For any connected graph which is not a Shannon
triangle of type $(2,2,2)$ or type $(2,2,1)$, either
$\chi_{\text{odd}}^{\prime}(G)\leq 3$, or there exists a special edge $e$
whose removal will make the graph odd $3$-edge-colorable.

In [4], an effort was already made towards the above conjecture. Note that an
equivalent way to express the conjecture is that, assuming
$\chi_{\text{odd}}^{\prime}(G)=4$, there exits an odd $4$-edge-coloring in
which color $4$ is used only once. Another related result, present in [7],
obtained a partial result by confirming the conclusion for the special class
of subdivisions of odd graphs. Now we are ready to state the first result of
this paper, which fully resolves the above conjecture positively.

######  Theorem 1.3.

For any connected graph $G$ that is not a Shannon graph of type $(2,2,2)$ or
$(2,2,1)$, either $\chi_{\text{odd}}^{\prime}(G)\leq 3$ or $G$ admits an odd
$4$-edge-coloring such that one of the four colors is used only once for some
edge $e$. Clearly, in the latter case,
$\chi_{\text{odd}}^{\prime}(G\backslash\\{e\\})=3$.

Now we move to graph coverability. Pyber also inquired in [8] whether three
colors are sufficient to give an odd edge-covering for any simple graph $G$, a
question later confirmed by Mátrai [2].

######  Theorem 1.4.

([2]) For any connected simple graph $G$, $\text{cov}_{\text{odd}}(G)\leq 3$.

This result was later partially generalized by Petruševski and Škrekovski [5]
to multigraphs. Moreover, as a connection between
$\chi_{\text{odd}}^{\prime}(G)$ and $\text{cov}_{\text{odd}}(G)$, as well as a
tool to obtain more structural information about edge-colorings and edge-
coverings, Petruševski and Škrekovski [5] defined the overlapping function.
More precisely, for an edge-covering $\phi:E(G)\to
2^{[k]}\backslash\emptyset$, let $\text{ovl}(\phi)$ be the sum of sizes of all
images under $\phi$ that are not singletons. The following are some examples
of the values of the function $\text{ovl}(\phi)$:

$\text{ovl}(\phi)=\begin{cases}0,&\text{ if }\phi\text{ is an edge-
coloring.}\\\ 2,&\text{ if }\phi\text{ has exactly one edge receiving two
colors, with others receiving one color.}\\\ 3,&\text{ if }\phi\text{ has
exactly one edge receiving three colors, with others receiving one color. }\\\
4,&\text{ if }\phi\text{ has exactly two edges receiving two colors each, with
others receiving one color.}\end{cases}$

Given a graph $G$ with $\text{cov}_{\text{odd}}(G)\leq 3$, define

(1.1) $\min\text{ovl}(G)=\min_{\phi}\text{ovl}(\phi),$

where the minimum is taken over all odd 3-edge-coverings $\phi$ of $G$.
Immediately after the definitions, if $G$ is odd 3-edge-colorable, then
$\min\text{ovl}(G)=0$. As the main result in [5], it was proved that except
for a list of multigraphs with exactly $3$ vertices, for any other connected
graph $G$, one has $\min\text{ovl}(G)\in\\{0,2,3,4\\}$. In the same paper, it
was also shown that there do exist multigraphs $G$ for which
$\min\text{ovl}(G)$ is at least $4$. So this leads to the following natural
conjecture.

######  Conjecture 1.5.

(Conjecture 2.5 of [6]) There is no simple graph $G$ such that
$\min\text{ovl}(G)=4$.

Our second result of this paper strongly confirms the above conjecture.

######  Theorem 1.6.

For any connected simple graph $G$, we have $\min\text{ovl}(G)\leq 2$.

Below, in Section 2, we start with a brief overview of notation and
preliminary results. Subsequently, in Section 3, we will address some
important special cases, obtaining certain partial results. We then proceed to
prove Theorem 1.3 in Section 4 and Theorem 1.6 in Section 5.

##  2\. Notation and Preliminary Results

In this section, we introduce some notation that we will frequently use in
this work. Given a graph $G$, we define a bouquet $\mathcal{B}$ as the set of
parallel edges on a pair of adjacent vertices. For any two adjacent vertices
$v$ and $u$, let $\mathcal{B}_{vu}$ denote the edge set incident to $v$ and
$u$. Given a loopless graph $G$, define a reduction graph $\text{red}(G)$ to
be the spanning subgraph of $G$ where each bouquet $\mathcal{B}$ is reduced to
size $1$ if it has an odd size, and to size $2$ if it has an even size. It was
proved in [1] that the odd chromatic index of the reduction graph
$\text{red}(G)$ is greater than or equal to that of $G$. It follows that for
any loopless graph $G$, if $\text{red}(G)$ satisfies the conclusion of Theorem
1.3, then the same is true for $G$. Therefore, below we will only consider
reduced graphs, that is, graphs satisfying $G=\text{red}(G)$.

A vertex $v$ is a cut vertex if $G-v$ is disconnected; otherwise, it is called
an internal vertex. Let $v$ be a cut vertex of $G$, and let
$C_{1},\cdots,C_{k}$ be the connected components of $G-v$. Then each
$G[V(C_{i})\cup\\{v\\}]$, for $i=1,\cdots,k$, is called a $v$-lobe of $G$. A
block of a graph $G$ is a maximal connected subgraph of $G$ that contains no
cut vertices. For a block $B$ of a graph $G$, the collection of internal
vertices in $B$ is denoted by $Int_{G}(B)$. If a block of $G$ contains at most
one cut vertex of $G$, we say it is an end-block of $G$. For each vertex $v\in
V(G)$, let $E_{G}(v)$ be the set of edges that are incident to $v$, and
$N_{G}(v)$ be the set of neighbors of $v$ in $G$. In a reduced graph $G$,
$N_{G}^{\prime}(v)$ denotes the set of neighbors of $v$ in a bouquet of size
1, and $N_{G}^{\prime\prime}(v)$ denotes the set of neighbors of $v$ in a
bouquet of size 2. Let $T$ be an even-sized subset of $V(G)$. We define a
spanning subgraph $H$ of $G$ to be a $T$-join if $d_{H}(v)$ is odd for all
$v\in T$ and even for all $v\notin T$.

The following lemmas contain some long-known facts.

######  Lemma 2.1.

(Proposition 2.5 of [4]) If $G$ is a connected graph that contains a bridge
then $\chi_{\text{odd}}^{\prime}(G)\leq 3$.

######  Lemma 2.2.

([2] and [6]) Any forest $F$ is odd $2$-edge-colorable.

Moreover, for a fixed vertex $v$ in $F$, any local coloring of $E_{F}(v)$ that
uses at most two colors extends to a 2-edge-coloring of $F$ that is odd away
from $v$.

For the first statement above, we can start by considering any vertex $v\in
F$. If $d_{F}(v)$ is odd, we can assign color $1$ to $E_{F}(v)$. If $d_{F}(v)$
is even, we can assign colors $1$ and $2$ to $E_{F}(v)$ arbitrarily, ensuring
that both colors are used an odd number of times. Then, one can greedily
extend the above coloring to an odd $2$-edge-coloring of $F$.

######  Lemma 2.3.

([9]) Let $G$ be a connected graph and let $T\subseteq V(G)$ be an even-sized
subset. Then there exists a $T$-join of $G$ that can be either a forest or a
coforest.

Let us remark that the second part of Theorem 1.1 follows directly from the
above lemma.

######  Lemma 2.4.

(Proposition 2.6 of [4]) Let $G$ be a connected graph and $v$ be an internal
vertex. Let $T\subseteq V(G)$ be an even-sized set. Then there exists a
$T$-join $H$ of $G$ which is a coforest, such that the following additional
property holds for $v$ in $\hat{H}$, where $\hat{H}=G\backslash E(H)$.

  1. (a)

If either $d_{G}(v)$ is odd and $v\in T$, or $d_{G}(v)$ is even and $v\notin
T$, then $d_{\hat{H}}(v)=0$.

  2. (b)

If either $d_{G}(v)$ is odd and $v\notin T$, or $d_{G}(v)$ is even and $v\in
T$, then $d_{\hat{H}}(v)=1$.

Moreover, in Case (b), we can indicate a specific edge $e$ incident to $v$
such that $e\in E(\hat{H})$.

Recall that a block graph is a connected graph admitting no cut vertex. The
following lemma is elementary and we omit its proof.

######  Lemma 2.5.

Let $G$ be a block graph with at least three vertices. Then for any three
distinct vertices of $G$, there is a path which joins any two of them and
contains the third vertex.

##  3\. Some Special Cases

Aiming to prove our two main theorems, in this section, we present some
preliminary results dealing with special cases. Note that some important
partial results will already be obtained in this section. For example, Theorem
1.3 will be proved under the condition that the graph $G$ admits at least one
cut vertex. We divide this section into two subsections for edge-colorings and
edge-coverings, respectively. Certain arguments are based on the various
coloring and covering schemes provided in [4] and [5], respectively.

###  3.1. Odd-Edge-Colorings

Let $S_{\ell}$ be a star graph with $\ell$ leaves. When $\ell=1$, we regard
one vertex as a leaf and the other vertex as the center, instead of two
leaves. We write $c(G)$ to denote the number of connected components of $G$.
The following technical lemma assists in identifying an edge of interest in a
fixed tree.

######  Lemma 3.1.

Let $T$ be a tree with $|V(T)|\geq 3$. Let $M$ be a subgraph of $T$,
satisfying the following conditions.

  1. (1)

each connected component of $M$ is either a copy of $S_{1}$ or a copy of
$S_{2}$, whose leaves are also leaves of $T$.

  2. (2)

the total number of leaves of all the connected components of $M$ is even.

  3. (3)

$c(M)\geq 2$, and at least two connected components of $M$ are $S_{1}$’s.

Then there is an edge $e$ of $T\setminus E(M)$ such that
$T\backslash\\{e\\}=L\cup R$ is a union of two subtrees, $L$ and $R$, and the
number of leaves in both connected components $M\cap L$ and $M\cap R$ is odd.

###### Proof.

Assume for contradiction that $T$ is a tree with the smallest number of edges
that admits some subgraph $M$ satisfying the three conditions, and the pair
$(T,M)$ fails to satisfy the intended conclusion. By assumption, we can find
two components of $M$ which are $S_{1}$’s. Let $u$ and $v$ denote their center
vertices, respectively. Let $P_{uv}$ be the path in the tree $T$ joining
vertices $u$ and $v$, and let $e$ be any edge in this path. Let us write
$T\backslash\\{e\\}=L\cup R$, a union of two subtrees. By the assumption for
$T$, the number of leaves in all the connected components of $M\cap L$ is
even, and $M\cap L$ has at least one $S_{1}$. This implies that there are at
least two $S_{1}$’s in $M\cap L$ and confirms condition (3). By the minimality
of $T$, in $L$ we can find an edge $f$ such that $L\backslash\\{f\\}$ is a
union of two subtrees $T_{1}\cup T_{2}$, each of which intersects $M$ with an
odd number of leaves. Observe that exactly one of these two subtrees, say
$T_{2}$, contains an end-vertex of $e$. Therefore, $T\backslash\\{f\\}$ is a
union of two trees $T_{1}\cup(T_{2}\cup\\{e\\}\cup R)$, and the number of
leaves of all the connected components of $T_{1}\cap M$ is odd, which is
absurd. ∎

We define that a graph $H$ has a minimum feedback vertex set (abbreviated as
$\min$ FVS) of size $1$ if $H$ contains a cycle and there exists a vertex $v$
such that $H-v$ is acyclic. We can refer to $v$ as a root of $H$. The
following lemma is the same with Proposition 2.3 in [6].

######  Lemma 3.2.

Let $H$ be a graph with a $\min$ FVS of size $1$, with a root $v$. Then there
exits an edge-coloring $\varphi:E(H)\to\\{1,2\\}$ such that for each $w\neq
v$, both colors 1 and 2 are odd at $w$. Moreover, if $d_{H}(v)$ is odd, then
color $1$ (respectively, color $2$) is odd (respectively, even) at $v$. If
$d_{H}(v)$ is even, then either both color degrees of $v$ are even, or both
are odd.

######  Lemma 3.3.

Let $H$ be a connected graph with a $\min$ FVS of size $1$, with a root $v$.
Assume $\chi_{\text{odd}}^{\prime}(H)=3$, $d_{H}(v)$ is even, and
$N_{H}^{\prime}(v)\geq 2$. Then there exists an edge $e$ of $H$ such that
$H\backslash\\{e\\}$ is odd $2$-edge-colorable.

###### Proof.

Suppose $d_{H}(v)=2k$, for some integer $k\geq 1$. We obtain a new graph
$H^{\prime}$ by blowing up the vertex $v$ into $2k$ distinct vertices,
$v_{1},v_{2},\cdots,v_{2k}$. Therefore $H^{\prime}$ is a forest and the
original edge set $E_{H}(v)$ becomes now $E(M)=\\{e_{1},\cdots,e_{2k}\\}$,
where $M=H^{\prime}[\\{v,v_{1},\cdots,v_{2k}\\}]$. The components of $M$ are
$S_{1}$’s and $S_{2}$’s, where there are at least two $S_{1}$’s since
$N_{H}^{\prime}(v)\geq 2$. Clearly, by Lemma 2.2, $H^{\prime}$ admits an odd
$2$-edge-coloring $\psi:E(H^{\prime})\to\\{1,2\\}$. The number of edges in
$\\{e_{1},e_{2},\cdots,e_{2k}\\}$ that are assigned with color $1$ (or color
$2$) is even; otherwise, $\psi$ induces an odd $2$-edge-coloring for $H$,
contradicting our assumption that $\chi_{\text{odd}}^{\prime}(H)=3$. Now we
consider the following cases.

Case 1.  There is a component of $H^{\prime}$ containing an odd number of
leaves of $M$.

Let $H_{1}$ be such a component, where there is an even number of edges of $M$
with one color, without loss of generality, color $1$, and an odd number of
edges of $M$ with color $2$. Then, in $H^{\prime}-H_{1}$, there are also an
even number of edges with color $1$ and an odd number of edges with color $2$.
We can switch colors $1$ and $2$ in $H_{1}$ such that there are an even number
of edges with color $2$ and an odd number of edges with color $1$. However,
this leads to an odd $2$-edge-coloring for $H$, a contradiction with
$\chi^{\prime}_{\text{odd}}(H)=3$.
Case 2.  Every component of $H^{\prime}$ has an even number of leaves of $M$.

Since $N_{H}^{\prime}(v)\geq 2$, there is a component $H_{1}$ that has at
least two $S_{1}$ stars in $M$. By Lemma 3.1, there is an edge $e$ of
$H_{1}\backslash\\{e_{1},\cdots,e_{2k}\\}$ such that $H_{1}\backslash\\{e\\}$
has one component $H_{1}^{\prime}$ with an odd number of leaves in $M$. We can
switch the edge colors in $H_{1}^{\prime}$, as in Case 1, and obtain an odd
2-edge-coloring of $H\backslash\\{e\\}$. Hence, $H\backslash\\{e\\}$ is odd
2-edge-colorable. ∎

The following two technical lemmas deal with graphs admitting cut vertices.

######  Lemma 3.4.

Suppose $G$ is connected with odd number of vertices and
$\chi^{\prime}_{\text{odd}}(G)\leq 4$. Let $v$ be a cut vertex of $G$. The
following are three cases to consider.

  1. Case 1.

there exists a $v$-lobe $G_{1}$ such that $v(G_{1})$ is even.

  2. Case 2.

there exists a $v$-lobe $G_{1}$ such that $d_{G_{1}}(v)$ is odd.

  3. Case 3.

$v$ has even degree and $|N^{\prime}_{G}(v)|\geq 2$.

In each of the above cases, either $G$ admits an odd $3$-edge-coloring, or
there exists an edge $e$ such that $G\backslash\\{e\\}$ admits an odd
$3$-edge-coloring:

###### Proof.

Case 1. $G_{1}$ is a $v$-lobe such that $v(G_{1})$ is even. Let
$G_{2}=G-(G_{1}-v)$, and note that $G_{2}$ is connected and $v(G_{2})$ is
even. If $d_{G_{1}}(v)$ is even, we arbitrarily choose one edge $e\in
E_{G_{1}}(v)$. Then we will prove that the graph $G\backslash\\{e\\}$ admits
an odd $3$-edge-coloring. So now we assume that $d_{G_{1}}(v)$ is odd. By
Lemma 2.4, we can take a spanning odd coforest $H_{1}$ for $G_{1}$, such that
for the edge complement $\hat{H}_{1}=G_{1}\backslash E(H_{1})$,
$d_{\hat{H}_{1}}(v)=0$. Similarly, we also take a spanning odd coforest
$H_{2}$ of $G_{2}$, and therefore $\hat{H}_{2}=G_{2}\backslash E(H_{2})$ is a
forest. Both $\hat{H}_{1}$ and $\hat{H}_{2}$ are odd $2$-edge-colorable. If
$d_{G_{1}}(v)$ is odd, we have $d_{\hat{H}_{1}}(v)=0$. We assign $E(H_{1})$
with color $1$, and provide an odd $2$-edge-coloring to $E(\hat{H}_{1})$ with
colors $2$ and $3$. We assign $E(H_{2})$ with color $2$, and assign color 1
(respectively, 3) to $E_{\hat{H}_{2}}(v)$ if $d_{\hat{H}_{2}}(v)$ is even
(respectively, odd). In either case, we then extend the edge coloring to a
$2$-edge-coloring for $E(\hat{H}_{2})$, which is odd-coloring at all vertices
of $H_{2}$ away from $v$, via Lemma 2.2. Thus, the resulting coloring is
indeed an odd $3$-edge-coloring for $G$.

Case 2. Suppose that there is a $v$-lobe $G_{1}$ such that $d_{G_{1}}(v)$ is
odd and write $G_{2}=G-(G_{1}-v)$. By Case 1, we can assume that every
$v$-lobe has odd order. In particular, $G_{1}$ has odd order. Let $H_{1}$ be a
spanning odd coforest of $G_{1}-v$ and then $\hat{H}_{1}=G_{1}\backslash
E(H_{1})$ is a graph with a $\min$ FVS of size $1$ with the root $v$. By Lemma
3.2, $\hat{H}_{1}$ admits a $2$-edge-coloring using colors $1$ and $2$, which
is odd at all vertices $w\neq v$, $w\in V(G_{1})$, moreover, color $1$ is odd
at $v$ and color $2$ is even at $v$. We assign color $3$ to $E(H_{1})$. If
$d_{G_{2}}(v)$ is even, we choose an arbitrary edge $e\in E_{G_{2}}(v)$. By
Lemma 2.1, $G_{2}\backslash\\{e\\}$ is connected. We only need to prove that
$G\backslash\\{e\\}$ is odd 3-edge-colorable. In the following, we provide an
odd 3-edge-coloring for $G$ when $d_{G_{2}}(v)$ is odd. We take a spanning
coforest $H_{2}$ in $G_{2}-v$ and then $\hat{H}_{2}=G_{2}\backslash E(H_{1})$
is a graph with a $\min$ FVS of size $1$, with a root $v$. We assign
$E(H_{2})$ with color $3$, and then use colors $1$ and $2$ to give
$\hat{H}_{2}$ an $2$-edge-coloring, which is an odd coloring at every vertex
$w\neq v$, $w\in V(G_{2})$, and color $1$ is even at $v$ and color $2$ is odd
at $v$. This gives an odd $3$-edge-coloring for $G$.

Case 3. Considering both Case $1$ and Case $2$, we can assume that every
$v$-lobe has an odd size, and $v$ has an even degree in every $v$-lobe. That
is, each component of $G-v$ has an even size, and then we apply Lemma 2.3 to
obtain an odd factor in each component. Thus, we denote the union of these odd
factors as $F$ and assign color $1$ to $E(F)$. The graph $\hat{F}=G\backslash
E(F)$ is either a forest, or a graph with a $\min$ FVS of size $1$, with a
root $v$. If $\hat{F}$ is a forest, we can give it an odd $2$-edge-coloring,
meaning that $G$ is odd $3$-edge-colorable. If $\hat{F}$ has a $\min$ FVS of
size $1$, we can apply Lemma 3.3 to choose one edge $e$ of $\hat{F}$ such that
$\hat{F}\backslash\\{e\\}$ is odd $2$-edge-colorable. This implies that
$G\backslash\\{e\\}$ is odd $3$-edge-colorable, completing the proof. ∎

######  Lemma 3.5.

Suppose $G$ is connected with odd order and $\chi^{\prime}_{\text{odd}}(G)=4$.
Assume $G$ admits a cut vertex $v$ with $N_{G}^{\prime}(v)=0$. Then there is
an edge $e$ such that $G\backslash\\{e\\}$ admits an odd $3$-edge-coloring.

###### Proof.

We consider $G$ to be a minimal counter-example. Since $N_{G}^{\prime}(v)=0$,
the degree of $v$ in every $v$-lobe is even. By Lemma 3.4, we can assume every
$v$-lobe has odd order.

Let $G_{1}$ be an arbitrary $v$-lobe and $G_{2}=G-(G_{1}-v)$. If $G_{2}$ is of
connectivity $1$, then the minimal choice of $G$ and Lemma 3.4 suggest that
either $\chi_{\text{odd}}^{\prime}(G_{2})\leq 3$, or we can select an edge $e$
in $G_{2}$ such that $\chi_{\text{odd}}^{\prime}(G_{2}\backslash\\{e\\})=3$.
In either case, we assume that color $1$ is assigned to some edge(s) incident
to $v$ either in $G_{2}$ or in $G_{2}\backslash\\{e\\}$. Note that $v$ is an
internal vertex of $G_{1}$. According to Lemma 2.4 (a), setting $T=G_{1}-v$,
there exists a $T$-join $H$ of $G_{1}$, which is a coforest and
$d_{\hat{H}}(v)=0$. We assign color 1 to $E(H)$ and obtain an odd $2$-edge-
coloring of $\hat{H}$ with colors $2$ and $3$. Thus, we conclude that either
$\chi_{\text{odd}}^{\prime}(G)\leq 3$, or we can find an edge (in $G_{2}$)
such that $G\backslash\\{e\\}$ is odd 3-edge-colorable.

Next, we assume $G_{2}$ is a block graph. Let $u$ be a neighbor of $v$ in
$G_{1}$ and $e\in\mathcal{B}_{vu}$. Write
$G_{1}^{\prime}=G_{1}\backslash\\{e\\}$. We observe that
$d_{G_{1}^{\prime}}(v)$ is odd and $d_{G_{2}}(v)$ is even. By Lemma 2.3, we
can find an odd factor $H$ of $G_{1}^{\prime}-v$. Then,
$\hat{H}=G_{1}^{\prime}\backslash E(H)$ is a graph with a $\min$ FVS of size
$1$, for which $v$ is a root. Since $d_{\hat{H}}(v)$ is odd, Lemma 3.2 implies
that $\hat{H}$ admits a $2$-edge-coloring odd away from $v$, where color $1$
is odd at $v$, while color $2$ is even at $v$.

Now, in $G_{2}$, we define the set $T=\\{x\in G_{2}-v:d_{G}(x)\text{ is
even}\\}$. If $T$ is empty, then we assign colors $2$ and $3$ to each edge of
the bouquet $\mathcal{B}_{wv}$, respectively, where $w$ is a neighbor of $v$
in $G_{2}$. All the other edges in $E(G_{2})$ are assigned color $1$. We can
check that this yields an odd 3-edge-coloring for $G\backslash\\{e\\}$. If $T$
is not empty, according to Lemma 2.3, we can select a forest $F$ which is a
$T$-join in $G_{2}$. If $d_{F}(v)=0$, we update $F$ to ensure that $v$ is
incident to at least one edge of $F$. Specifically, let $u_{1}$ and $u_{2}$ be
two vertices in $T$ such that there exists a path $P\subseteq F$ connecting
them. By Lemma 2.5, there exists a path $Q$ connecting $u_{1}$ and $u_{2}$
passing through $v$. We then update $F$ by excluding $E(P)$, including $E(Q)$,
and then deleting all the cycles (if any). It can be checked that $F$ remains
to be a $T$-join, and now we confirm that $d_{F}(v)>0$. Let
$\hat{F}=G_{2}\backslash E(F)$, where the only even vertex in $\hat{F}$ is
$v$. Next, we apply an odd edge-coloring to the edges of $F$ using colors 2
and 3. By the previous argument, both colors $2$ and $3$ appear an odd number
of times at $N_{F}(v)$. Therefore, we can assign the edges of $E(\hat{F})$
with color $1$. One can check that this procedure completes an odd $3$-edge-
coloring of $G\backslash\\{e\\}$. ∎

We remark that the above two lemmas already imply Theorem 1.3 in the special
case when the graph $G$ admits a cut vertex.

The following two lemmas are based on Corollary 3.3 and Lemma 3.4 in [4],
respectively.

######  Lemma 3.6.

Let $G$ be a connected graph, and let $v$ and $w$ be odd vertices such that
$w\in N_{G}^{\prime\prime}(v)$. If $v$ is an internal vertex of $G$ and $w$ is
an internal vertex of $G-v$, then there exists an edge $f$ such that
$G\backslash\\{f\\}$ admits an odd $3$-edge-coloring.

###### Proof.

Write $\mathcal{B}_{vw}=\\{e,f\\}$. Since $w$ is an internal vertex of $G-v$,
by Lemma 2.4, there is a spanning odd coforest $H$ in $G-v$ such that
$d_{\hat{H}}(w)=0$, where $\hat{H}=(G-v)\backslash E(H)$. We assign color $1$
to $E(H)$. Note that $d_{G}(v)$ is odd, and the graph $G\backslash E(H)$ has a
$\min$ FVS of size $1$, with a root $v$. By Lemma 3.2, $G\backslash E(H)$
admits a $2$-edge-coloring using colors 2 and 3, which is an odd coloring away
from $v$. Moreover, color $2$ is odd at $v$ and color $3$ is even at $v$.
Clearly, we can assume that for the edge set $\mathcal{B}_{vw}=\\{e,f\\}$,
edge $e$ receives color $2$ and edge $f$ receives color $3$. This induces a
coloring of the graph $G\backslash\\{f\\}$, which is an odd $3$-edge-coloring.
∎

######  Lemma 3.7.

Let $G$ be a connected graph, and assume that every even vertex $u$ satisfies
$N_{G}^{\prime}(u)=0$. Three vertices $v,w,q\in V(G)$ satisfy the following.

  1. (1)

$v$ is an even internal vertex of $G$.

  2. (2)

$q$ is an internal vertex of $G-v$.

  3. (3)

$v$ and $q$ are nonadjacent, and $w$ is adjacent to both $v$ and $q$.

Then either $G$ admits an odd $3$-edge-coloring, or there is an edge $e$ such
that $G\backslash\\{e\\}$ admits an odd $3$-edge-coloring.

###### Proof.

We discuss $4$ cases based on the parities of $d_{G}(w)$ and $d_{G}(q)$. We
write $\mathcal{B}_{vw}=\\{f_{1},f_{2}\\}$ and specify one edge
$e\in\mathcal{B}_{wq}$.

Case 1. $d_{G}(w)$ is odd and $d_{G}(q)$ is even. Since $q$ is an even
internal vertex in $G-v$, according to Lemma 2.4, there is an odd spanning
coforest $H$ in $G-v$, such that $E_{\hat{H}}(q)=\\{e\\}$, where
$\hat{H}=(G-v)\backslash E(H)$. Note that $d_{\hat{H}}(w)$ is even, and
$d_{\hat{H}}(w)\geq 2$ since $e$ is present. By Lemma 3.2,
$G\backslash(E(H)\cup\\{f_{1},e\\})$ has a 2-edge-coloring $\phi$ such that
$\phi$ is odd away from $v$, color $1$ is odd at $v$ and color $2$ is even at
$v$. Since the degree of $w$ in $G\backslash(E(H)\cup\\{f_{1},e\\})$ is even,
it has received both colors $1$ and $2$. Then we assign $\\{e,f_{1}\\}$ with
color 2 and $E(H)$ with color 3. This procedure yields an odd 3-edge-coloring
for $G$.

Case 2. $d_{G}(w)$ is even and $d_{G}(q)$ is odd. We write
$\mathcal{B}_{wq}=\\{e,e^{\prime}\\}$. Note the graph
$G\backslash\\{e^{\prime}\\}$ has a similar property with Case $1$, by
exchanging the roles of $v$ and $q$. Therefore, a similar argument gives an
odd $3$-edge-coloring for the graph $G\backslash\\{e^{\prime}\\}$.

Case 3. $d_{G}(w)$ is odd and $d_{G}(q)$ is odd. Choose $e^{\prime}\in
E_{G}(q)\backslash E_{G}(w)$. Then $G\backslash\\{e^{\prime}\\}$ admits an odd
$3$-edge-coloring as it satisfies condition of Case 1.

Case 4. $d_{G}(w)$ is even and $d_{G}(q)$ is even.  We again write
$\mathcal{B}_{wq}=\\{e,e^{\prime}\\}$. There exists a spanning odd coforest
$H$ of $G-v$ satisfying $E_{\hat{H}}(q)=e$. Similar with Case 1, by Lemma 3.2,
we can give a 2-edge-coloring $\phi$ with colors 1 and 2 for
$G^{\prime}=G\backslash(E(H)\cup\\{e,f_{1}\\})$ such that $\phi$ is odd away
from $v$, color $1$ is odd at $v$, and color $2$ is even at $v$. Note that
$d_{G^{\prime}}(w)$ is odd, which implies that, via Lemma 2.2, we can ask $w$
to receive only one color in $\phi$. If $w$ receives color $1$, then we assign
color $2$ for $f_{1}$, color $3$ for $E(H)$ and delete edge $e$, which is an
odd $3$-edge-coloring for $G\backslash\\{e\\}$. If $w$ receives color $2$,
then we assign color $2$ to both $f_{1}$ and $e$. It can be checked that this
is an odd $3$-edge-coloring for $G$. ∎

We would like to address another very special case when $G$ is a complete
graph with all adjacent vertices connected by double edges.

######  Lemma 3.8.

Suppose $G$ is a complete graph with order $2\ell+1$, $\ell\geq 2$, and each
bouquet $\mathcal{B}_{vw}$ has size 2 for any $v,w\in V(G)$. Then, for any
edge $e$, the graph $G\backslash\\{e\\}$ is odd $3$-edge-colorable.

###### Proof.

Let us specify two vertices $x$ and $y$ in $V(G)$, and let $H=G-\\{x,y\\}$,
which is a copy of $K_{2\ell-1}$. Let $v$ be any vertex in $V(H)$. We can
split $E(H)$ into a union of three edge sets (regarded as subgraphs): $H_{1}$,
$H_{2}$, and an edge $e\in\mathcal{B}_{v_{1}v_{2}}$, where $v_{1}$ and $v_{2}$
are two fixed vertices in $H$. We require that the subgraph $H_{1}$
(respectively, $H_{2}$) has even degree at the vertex $v_{1}$ (respectively,
$v_{2}$), and odd degree at all other vertices in $V(H)$. For example, we can
take $H_{1}$ to be the union of a star $S_{2}$ centered at $v_{1}$ with two
leaves $v_{2}$ and $v_{3}$, together with a perfect matching in
$H-\\{v_{1},v_{2},v_{3}\\}$. Then $H_{2}=H\backslash(E(H_{1})\cup\\{e\\})$. We
then define the graph $H_{1}^{\prime}$ to be the union of $H_{1}$ and all the
bouquets $\mathcal{B}_{xw}$ for $w\in V(H)-v_{1}$ and one of the edges from
the bouquet $\mathcal{B}_{xv_{1}}$. We can observe that $H_{1}^{\prime}$ is an
odd graph. Similarly, we define $H_{2}^{\prime}$ to be a union of $H_{2}$ and
all the bouquets $\mathcal{B}_{yw}$ for $w\in V(H)-\\{v_{2}\\}$, along with
one of the edges from the bouquet $\mathcal{B}_{yv_{2}}$. The remaining graph
$H_{3}=G\backslash(E(H_{1}^{\prime})\cup E(H_{2}^{\prime}))$ is the union of
$\mathcal{B}_{xy}$ and one edge from $\mathcal{B}_{xv_{1}}$ and one edge from
$\mathcal{B}_{yv_{2}}$, which is an odd subgraph. We assign color $1$ to
$H_{3}$, color $2$ to $H_{1}^{\prime}$, and color $3$ to $H_{2}^{\prime}$.
This is an odd $3$-edge-coloring for $G\backslash\\{e\\}$. ∎

The following lemma reveals an important structure where a particular even
vertex $v$ satisfies $N^{\prime}_{G}(v)=0$ and is adjacent to every vertex of
a path. There are two ways of a $2$-edge-coloring, both of which are odd at
all vertices $w\neq v$. In the first, both colors $1$ and $2$ are odd at the
vertex $v$, while in the other, both are even. This flexibility in coloring
will be important later.

######  Lemma 3.9.

Let $G$ be a graph with $v(G)\geq 4$, and let $v$ be an even vertex such that
$N_{G}(v)=N_{G}^{\prime\prime}(v)=V(G-v)$. Moreover, suppose $G-v$ is a simple
path. Then we can obtain two distinct $2$-edge-colorings
$\varphi_{1},\varphi_{2}:E(G)\to\\{1,2\\}$ as follows.

  1. (1)

The first coloring $\varphi_{1}$ is an odd $2$-edge-coloring;

  2. (2)

The second coloring $\varphi_{2}$ is a $2$-edge-coloring which is odd at all
$w\neq v$, and both colors $1$ and $2$ are even at $v$.

###### Proof.

Let $\\{e_{1},e_{2},\cdots,e_{2k}\\}$ denote the edges that are incident to
$v$, and let $P_{k-1}=G-v$ be the path. The edge set of $P_{k-1}$ is denoted
by $\\{f_{1},f_{2},\cdots,f_{k-1}\\}$.

We define the first coloring $\varphi_{1}$ as follows. We assign color $1$ to
the following edges.

$\displaystyle\\{f_{1}\\},\\{f_{m}\big{|}\,m\text{ is even},2\leq m\leq
k-1\\},$ $\displaystyle\\{e_{1},e_{2},e_{3}\\},\text{ and
}\\{e_{2m+1},e_{2m+2}\big{|}\,m\text{ is even},2\leq m\leq k-1\\}.$

The remaining edges are assigned color $2$.

We define the second coloring $\varphi_{2}$ as follows. We assign color $1$ to
the following edges.

$\displaystyle\\{f_{m}\big{|}\,m\text{ is odd},1\leq m\leq k-1\\},$
$\displaystyle\\{e_{1},e_{2}\\},\,\text{ and
}\\{e_{2m+1},e_{2m+2}\big{|}\,m\text{ is odd},1\leq m\leq k-1\\}.$

The remaining edges are assigned color $2$. ∎

###  3.2. Odd-Edge-Coverings

######  Lemma 3.10.

Let $G$ be a connected simple graph with odd number of vertices. If $G$ admits
a cut vertex $v$ such that $G-v$ has a connected component with odd order,
then $\min\text{ovl}(G)\leq 2$.

###### Proof.

Let $C$ be a connected component of $G-v$ with $v(C)$ odd, and let
$D=G-(V(C)\cup\\{v\\})$. By Lemma 2.3, there are odd spanning coforests
$F_{1}$ and $F_{2}$ in $G[V(C)\cup\\{v\\}]$ and $G[V(D)\cup\\{v\\}]$
respectively. We also take them to have maximum sizes among all such odd
spanning coforests. Next, we obtain $T_{1}=G[V(C)\cup\\{v\\}]\backslash
E(F_{1})$ and $T_{2}=G[V(D)\cup\\{v\\}]\backslash E(F_{2})$. We assign colors
$1$ and $2$ to the edges of $F_{1}$ and $F_{2}$, respectively.

Case 1. $d_{T_{1}\cup T_{2}}(v)\leq 1$.

We assume that $d_{T_{1}}(v)\leq 1$ and $d_{T_{2}}(v)=0$. Then, we proceed to
provide an odd $2$-edge-coloring for $T_{1}$ using colors $2$ and $3$,
ensuring that $E_{T_{1}}(v)$ does not receive color 2. Subsequently, we give
an odd $2$-edge-coloring for $T_{2}$ using colors $1$ and $3$. As a result, we
conclude that $\chi^{\prime}_{\text{odd}}(G)=3$, and thus,
$\min\text{ovl}(G)=0$.

Case 2. $d_{T_{1}\cup T_{2}}(v)\geq 2$.

If $d_{G}(v)$ is odd, then $d_{T_{1}\cup T_{2}}(v)$ is also odd. Consequently,
we can derive an odd $3$-edge-coloring for $T_{1}\cup T_{2}$, consistent with
the coloring of $F_{1}$ and $F_{2}$ provided earlier. Initially, we ensure
that all edges incident to $v$ are assigned color $3$. Subsequently, for the
forest $T_{1}-v$, we utilize Lemma 2.2 to apply an odd $2$-edge coloring using
colors $2$ and $3$. Similarly, for the forest $T_{2}-v$, we obtain an odd
$2$-edge-coloring using colors $1$ and $3$. As a result, this yields an odd
$3$-edge-coloring for the entire graph $G$, leading to $\min\text{ovl}(G)=0$.

If $d_{G}(v)$ is even, we define an odd $3$-edge-covering $\varphi$ such that
$\text{ovl}(\varphi)=2$. Let $u\in F_{1}$ be a vertex adjacent to $v$. We
assert that

Claim. $T_{1}\cup T_{2}\cup\\{vu\\}$ contains no cycle.

Indeed, if $T_{1}\cup T_{2}\cup\\{vu\\}$ contains a cycle, the cycle must be
contained in $G[V(C)\cup\\{v\\}]$. Thus we can assume it has the form
$vuw_{1}\cdots w_{t}$. Then, we can update $F_{1}$ by removing the edge $vu$
and adding the path $w_{1}\cdots w_{t}$, to obtain an odd coforest in
$G[V(C)\cup\\{v\\}]$ which has larger size. This contradicts the maximum
choice of $F_{1}$. The claim follows.

Then, by Lemma 2.2, we can obtain an odd $2$-edge-coloring for $T_{1}\cup
T_{2}\cup\\{vu\\}$ with colors $3$ and $4$, such that all the edges incident
to $v$ are colored with $3$ since $d_{T_{1}\cup T_{2}\cup\\{vu\\}}(v)$ is odd.
Subsequently, we replace all edges colored with $4$ in $C$ (respectively, $D$)
with color $2$ (respectively, color $1$). Thus, we obtain an odd $3$-edge-
covering, where $vu$ is the only edge that receives two colors, namely, colors
$1$ and $3$. Consequently, $\min\text{ovl}(G)\leq 2$. ∎

Below we rephrase Claim 2 and Claim 3 in the proof of Theorem 1 in [5], only
for simple graphs in our context.

######  Lemma 3.11.

Let $G$ be a connected simple graph with odd order and $v$ be an even vertex
with $w\in N_{G}(v)$. We have the following:

  1. (a)

If $d_{G}(w)$ is even and $w$ is an internal vertex of $G-v$, then $G$ admits
an odd $3$-edge-coloring, which implies $\min\text{ovl}(G)=0$.

  2. (b)

If $d_{G}(w)$ is odd, and there exists an internal vertex $u$ of $G-v$, such
that $u\in N_{G-v}(w)$ and $u\notin N_{G}(v)$, then there is an odd $3$-edge-
covering $\varphi$ of $G$, with $\text{ovl}(\varphi)\leq 2$.

###### Proof.

Let $d_{G}(v)=2k$.

(a) Since $w\in N_{G}(v)$ and $d_{G}(w)$ is even, we observe that $d_{G-v}(w)$
is odd. As $w$ is an internal vertex of $G-v$, we can find an odd factor $H$
of $G-v$, which is a coforest and contains the entire $E_{G-v}(w)$. Let
$\hat{H}$ be the edge complement of $H$ in $G\backslash\\{vw\\}$. Clearly,
$\hat{H}$ is a graph with a $\min$ FVS of size $1$, with $v$ as a root.
Therefore, by Lemma 3.2, since $d_{\hat{H}}(v)$ is odd, there is a 2-edge-
coloring $\varphi:E(\hat{H})\to\\{1,2\\}$ that is odd away from $v$, and for
vertex $v$, color 1 is odd and color 2 is even. We then assign color $2$ to
the edge $vw$ and color $3$ to $E(H)$. Thus, an odd $3$-edge-coloring for $G$
is obtained.

(b) We discuss two cases depending on the parity of $d_{G}(u)$.

Case $1$. $d_{G}(u)$ is even. In $G-v$, by Lemma 2.4(b), we can find an odd
factor $H$, which is a coforest and contains $E_{G}(u)\backslash\\{wu\\}$. We
assign color $3$ to $E(H)$ and let $\hat{H}$ be the edge complement of $H$ in
$G\backslash\\{vw,wu\\}$. By Lemma 3.2, and observing that $d_{\hat{H}}(v)$ is
odd, there is an edge-coloring $\varphi:E(\hat{H})\to\\{1,2\\}$ that is odd
away from $v$, and for vertex $v$, color 1 is odd at $v$ and color 2 is even
at $v$. If $w$ is an isolated vertex in $\hat{H}$, then we can assign color
$2$ to the edge $vw$ and color $1$ to the edge $wu$. Otherwise, since
$d_{\hat{H}}(w)$ is even, the edge set $E_{\hat{H}}(w)$ obtains both colors
$1$ and $2$. We then assign color $2$ to both edges $vw$ and $wu$. This
results in an odd $3$-edge-coloring for $G$, which implies
$\min\text{ovl}(G)=0$.

Case $2$. $d_{G}(u)$ is odd. We find in $G-v$ an odd factor $H$, which is a
coforest and contains $E_{G}(u)$. We assign color $3$ to $E(H)$ and let
$\hat{H}$ be the edge complement of $H$ in $G\backslash\\{vw,wu\\}$. Again, by
Lemma 3.2, and observing that $d_{\hat{H}}(v)$ is odd, there is an edge-
coloring $\varphi:E(\hat{H})\to\\{1,2\\}$ that is odd away from $v$ with color
$1$ being odd at $v$ and color $2$ being even at $v$. Note that
$d_{\hat{H}}(w)$ is odd, so the edge set $E_{\hat{H}}(w)$ obtains exactly one
of the colors $1$ or $2$. If it obtains color $1$, then we assign color $2$ to
the edge $vw$, resulting in an odd $3$-edge-coloring $\varphi$, with
$\text{ovl}(\varphi)=0$. If it obtains color $2$, then we assign color $2$ to
both edges $vw$ and $wu$, resulting in the edge $wu$ receiving two colors in
this case. In either case, the covering yields an odd $3$-edge-covering $\phi$
for $G$, with $\text{ovl}(\phi)\leq 2$. ∎

The next corollary is a rephrasing of Claim 7 in the proof of Theorem 1 in
[5].

######  Corollary 3.12.

Let $G$ be a connected simple graph with odd number of vertices. Suppose $v$
is an even internal vertex of $G$ and $G-v$ contains no cut vertices. Then
$\min\text{ovl}(G)\leq 2$.

###### Proof.

Let $w$ be a neighbor of $v$, which is an internal vertex of $G-v$ by
assumption. Lemma 3.11 (a) implies that $d_{G}(w)$ is odd, and Lemma 3.11 (b)
implies that every neighbor $u$ of $w$ must also be a neighbor of $v$. By
repeatedly applying Lemma 3.11 and noticing that $G-v$ is connected, we
conclude that every vertex of $G-v$ has odd degree and is adjacent to $v$. Now
we list the set of common neighbors of $v$ and $w$ as
$\\{q_{1},\cdots,q_{2k}\\}$. We assign color $1$ to $wq_{j}$ and color $2$ to
$vq_{j}$ for each $j=1,\cdots,2k$. Then we assign both colors $1$ and $2$ to
the edge $vw$. Finally, note that the remaining edges form an odd graph, and
we assign color $3$ to them. ∎

##  4\. Proof of Theorem 1.3

This section is devoted to the proof of Theorem 1.3. The main strategy of the
proof involves searching for different coloring schemes that use only one of
the four colors once, given that $\chi_{\text{odd}}^{\prime}(G)=4$. For
example, we have already seen that this strategy works for the special case
when the graph admits a cut vertex, as discussed in the previous section.
There are two additional ingredients in the proof. The first ingredient is the
method of removing one edge from a certain tree or a graph with a $\min$ FVS
of size $1$, as demonstrated in Lemma 3.3. This removal gives us some freedom
to color the distinct components of the resulting forest separately. The
second ingredient is a dichotomous approach to two coloring schemes for a
specific graph, as demonstrated in Lemma 3.9. This flexibility is crucial for
addressing the various cases that emerge in subsequent arguments.

Now we begin the proof by considering a connected graph $G$ which is not a
Shannon triangle of type $(2,2,2)$ or type $(2,2,1)$. By Theorem 1.1, if $G$
has even order, then $\chi_{\text{odd}}^{\prime}(G)\leq 3$. If $v(G)=3$, it is
also not hard to conclude. Therefore, below we can safely assume that $G$ has
odd order and $v(G)\geq 5$. By comparing the parities, we observe that there
exists at least one even vertex in $G$. Let $\mathcal{E}$ (respectively,
$\mathcal{O}$) be the set of even (respectively, odd) vertices in $G$.
Moreover, according to Lemmas 3.4 and 3.5, we can assume that $G$ is a block
graph.

We then divide into two cases. In the first case, where there exists an even
vertex $v$ satisfying $|N_{G}^{\prime}(v)|>0$, the proof will be concise since
most of the groundwork has been covered in Section 3. In the second case,
where every even vertex $v$ satisfies $|N_{G}^{\prime}(v)|=0$, we will follow
some ideas from [4]. In particular, we will split the main argument into a
sequence of six claims to organize various coloring schemes for different
specific cases.

Case 1. There exists $v\in\mathcal{E}$ with $|N_{G}^{\prime}(v)|>0$.

The proof is similar to and simpler than the proof of Case 3 of Lemma 3.4.
Thus, we will only outline the arguments here. We apply Lemma 2.3 to $G-v$ to
obtain an odd spanning coforest $F$. Then, either $\hat{F}=G\backslash E(F)$
is a forest or it has a $\min$ FVS of size $1$, with a root $v$. We apply
Lemma 3.3 to find the edge $e$ that satisfies the conclusion of Theorem 1.3.

Case 2. For every $v\in\mathcal{E}$, $|N_{G}^{\prime}(v)|=0$.

Claim 1. Let $v\in\mathcal{E}$ and $B$ be an end-block of $G-v$, then
$\text{Int}_{G-v}(B)\subseteq N_{G}(v)=N_{G}^{\prime\prime}(v)$.

###### Proof.

By Lemma 3.7, we can see that every internal vertex of end-block $B$ is a
neighbor of $v$. ∎

Claim 2. There exists a vertex $v\in\mathcal{E}$ such that $G-v$ is not a
block graph.

###### Proof.

Suppose for a contradiction that for every vertex $v\in\mathcal{E}$ the graph
$G-v$ is a block graph. By Claim 1, for each $v\in\mathcal{E}$, we have
$N_{G}(v)=N_{G}^{\prime\prime}(v)=V(G)-v$.

If $|\mathcal{E}|=1$, we first observe that every vertex in $G-v$ has odd
degree. So there must exist a pair of vertices $u,w$ such that
$|\mathcal{B}_{uw}|=1$. Denote $e=uw$, and below we will show that removing
$e$ from $E(G)$ results in a graph $G^{\prime}=G\backslash\\{e\\}$ that admits
an odd $3$-edge-coloring. Since $G-v$ is a block graph, $G^{\prime}-v$ is
connected and there is a path $P$ in $G^{\prime}-v$ connecting $u$ and $w$. We
can see that $H=(G^{\prime}-v)\backslash E(P)$ is an odd graph. We assign
color $3$ to $E(H)$. List the vertex set of $G-v-V(P)$ as
$\\{v_{1},v_{2},\cdots,v_{m}\\}$ and write
$\mathcal{B}_{vv_{i}}=\\{e_{2i-1},e_{2i}\\}$ for each $i=1,\cdots,m$. Then the
edges of $\\{e_{i}\big{|}\,1\leq i\leq 2m,i\text{ is odd}\\}$ are assigned
with color $1$ and $\\{e_{i}\big{|}\,1\leq i\leq 2m,i\text{ is even}\\}$ are
assigned with color $2$.

Observe that by excluding isolated vertices, the remaining graph of
$G^{\prime}\backslash E(H)$ has exactly the same structure as described in
Lemma 3.9. If $m$ is even, we follow the first way in Lemma 3.9 to give it a
$2$-edge-coloring. If $m$ is odd, we choose the second way. In either case, we
eventually obtain an odd $3$-edge-coloring for
$G^{\prime}=G\backslash\\{e\\}$.

For the case where $|\mathcal{E}|\geq 3$, according to Lemma 3.8, $G$ must
have at least two odd vertices. Moreover, there must exist two adjacent odd
vertices as $y$ and $z$, for which $|\mathcal{B}_{yz}|=1$. Let us select a
triplet of vertices $v,w,x$ from $\mathcal{E}$. Now, we denote
$\mathcal{B}_{vy}=\\{e^{\prime},e^{\prime\prime}\\}$ and
$\mathcal{B}_{wz}=\\{f^{\prime},f^{\prime\prime}\\}$. We define
$T=V(G)-\\{v,w,x,y,z\\}$ as the set containing an even number of vertices.
Below we will define $H$ to be a $T$-join in $G-\\{v,w,x\\}$, which is also a
coforest.

Specifically, let $p_{1},\cdots,p_{2\ell}$ and $o_{1},\cdots,o_{2k}$ represent
the even and odd vertices in $T$, respectively. It is worth noting that $\ell$
and $k$ can be zero. When both $\ell$ and $k$ are zero, $H$ is an empty graph.
Otherwise, by definition, the edge set $E(H)$ comprises the following parts:

  1. (1)

$E(G[\mathcal{O}])\backslash\\{yz\\}$;

  2. (2)

All the bouquets $\mathcal{B}_{p_{i}p_{i}^{\prime}}$, for
$i,i^{\prime}=1,\cdots,2\ell$ and $i\neq i^{\prime}$,
$\mathcal{B}_{p_{i}o_{j}}$, and $\mathcal{B}_{p_{i}z}$, for
$i=1,\cdots,2\ell$, $j=1,\cdots,2k$;

  3. (3)

one of the edges in each bouquet $\mathcal{B}_{p_{i}y}$, for $i=\cdots,2\ell$.

We then denote $\hat{H}=(G-\\{v,w,x\\})\backslash E(H)$ as the edge complement
of $H$ in $G-\\{v,w,x\\}$. In fact, by definition, $\hat{H}$ is an odd star
centered at $y$, with the vertices $z$, $p_{1},\cdots,p_{2\ell}$ being the
leaves.

Consider the graph $G\backslash\\{e^{\prime\prime}\\}$. We assign color $1$ to
$E(H)\cup\\{e^{\prime},f^{\prime}\\}\cup\mathcal{B}_{vz}$, color $2$ to
$\mathcal{B}_{xz}\cup\\{f^{\prime\prime}\\}$, and color $3$ to $E(\hat{H})$.
For each $p_{i}$, $i=1,\cdots,2\ell$, assign color $3$ to
$\mathcal{B}_{p_{i}x}$ and also to $\mathcal{B}_{yx}$. For each $o_{j}$,
$j=1,\cdots,2k$, the two edges in $\mathcal{B}_{o_{j}x}$ are assigned colors
$2$ and $3$, respectively. It can be verified that so far there are an even
number of colors 2 and 3 at $x$. Next, we assign the two edges in
$\mathcal{B}_{vx}$ with colors $2$ and $3$, respectively, assign both edges in
$\mathcal{B}_{wx}$ with color $2$, and assign all other still uncolored edges
of $G$ with color $1$. One can verify that this yields an odd $3$-edge-
coloring for $G\backslash\\{e^{\prime\prime}\\}$. ∎

Following Claim 2, we choose $v\in\mathcal{E}$ such that $G-v$ is not a block
graph. For the next three claims, we fix an end-block $B$ of $G-v$ and denote
by $s$ the unique cut vertex of $G-v$ that belongs to $V(B)$.

Claim 3. $\text{Int}_{G-v}(B)\subseteq\mathcal{O}$.

###### Proof.

Suppose $w$ is an even vertex in $\text{Int}_{G-v}(B)$. Let $B^{\prime}$ be
another end-block of $G-v$, and $w^{\prime}\in\text{Int}_{G-v}(B^{\prime})$.
Note that there is no edge incident to both $w$ and $w^{\prime}$, and $v$ is a
common neighbor of $w$ and $w^{\prime}$. We apply Lemma 3.7 to the triple
$\\{w,v,w^{\prime}\\}$ and conclude that $w^{\prime}$ is a cut vertex of
$G-w$, which means that $G-\\{w,w\\}$ must be a disconnected graph. This has
several strong implications. Firstly,
$\text{Int}_{G-v}(B^{\prime})=\\{w^{\prime}\\}$. Then, together with Claim 1,
it follows that $\text{Int}_{G-v}(B)=\\{w\\}$. Finally,
$N_{G}(v)=N^{\prime\prime}_{G}(v)=\\{w,w^{\prime}\\}$. Recall that $s$ is the
unique cut vertex of $G-v$ contained in $B$. Here we also denote by
$s^{\prime}$ the unique cut vertex of $G-v$ in $B^{\prime}$ (note that it is
possible that $s=s^{\prime}$). As a particular consequence of the above
arguments, we see $v$ and $s$ (or $s^{\prime}$) are non-adjacent. Note that
$|\mathcal{B}_{ws}|=2$ since $w$ is an even vertex.

In the graph $G-\\{v,w,w^{\prime}\\}$, we apply Lemma 2.3 to find an odd
spanning coforest $H$, and write $\hat{H}=(G-\\{v,w,w^{\prime}\\})\backslash
E(H)$. Choose one edge $e\in\mathcal{B}_{w^{\prime}s^{\prime}}$. Then we
assign color $3$ to $E(H)$, and use colors $1$ and $2$ to give $E(\hat{H}+e)$
an odd $2$-edge-coloring such that the edge $e$ receives color $1$. Then, we
assign color $3$ to both edges in $\mathcal{B}_{sw}$, assign color $1$ to both
edges in $\mathcal{B}_{vw^{\prime}}$, and assign colors $1$ and $3$ to the two
edges in $\mathcal{B}_{vw}$, respectively. If
$|\mathcal{B}_{w^{\prime}s^{\prime}}|=1$, then we have already obtained an odd
$3$-edge-coloring for $G$. Otherwise, let us denote by $e^{\prime}$ the other
edge in $\mathcal{B}_{w^{\prime}s^{\prime}}$ other than $e$. Then, the graph
$G\backslash\\{e^{\prime}\\}$ admits an odd $3$-edge-coloring. ∎

Claim 4. The graph $B-s$ is a simple graph.

###### Proof.

Suppose that we find vertices $w^{\prime}$ and
$w^{\prime\prime}\in\text{Int}_{G-v}(B)$ such that
$|\mathcal{B}_{w^{\prime}w^{\prime\prime}}|=2$. Note that by Claim 3,
$w^{\prime},w^{\prime\prime}\in\mathcal{O}$. From Claim 1 we know that $v$ is
adjacent to all vertices in $\text{Int}_{G-v}(B)$. And also $s$ and $v$ is
connected in $G-\text{Int}_{G-v}(B)$. It follows that $G-w^{\prime}$ and
$G-\\{w^{\prime},w^{\prime\prime}\\}$ are both connected. We then apply Lemma
3.6 to conclude the proof. ∎

Claim 5. $s\in\mathcal{O}$ and $\text{Int}_{G-v}(B)\cap
N_{G}^{\prime\prime}(s)=\emptyset$.

###### Proof.

Suppose $s\in\mathcal{E}$. Lemma 3.7 implies that
$\text{Int}_{G-v}(B)\subseteq N_{G}(s)=N_{G}^{\prime\prime}(s)$. Take any
$w\in\text{Int}_{G-v}(B)$, then Claim 1 and Claim 4 imply
$N_{G}^{\prime\prime}(w)=\\{v,s\\}$. Since $d_{G}(w)$ is odd,
$N_{G}^{\prime}(w)$ consists of an odd number of internal vertices in $B$,
listed as $\\{u_{1},\cdots,u_{2\ell+1}\\}$. For each $j=1,\cdots,2\ell+1$,
choose one edge $e_{j}\in\mathcal{B}_{vu_{j}}$. Let $T$ be the set of all even
vertices in the graph $G-v-(B-\\{s\\})$. Clearly, $T$ has even size and
contains $s$. We apply Lemma 2.3 to find a forest $F$ which is also a
$T$-join.

Let $\mathcal{B}_{ws}=\\{e,e^{\prime}\\}$. Now we consider the graph
$G^{\prime}=G\backslash\\{e^{\prime}\\}$. With Lemma 2.2, we can assign color
$1$ to all $E_{F}(s)$ and extend it to an odd $2$-edge-coloring to the whole
$F$. We then assign color $1$ to $\\{wu_{1},\cdots,wu_{2\ell+1}\\}$, and
assign color $2$ to
$\\{e_{1},\cdots,e_{2\ell+1}\\}\cup\mathcal{B}_{vw}\cup\\{e\\}$. One can
verify that the remaining edges of $G^{\prime}$ form an odd graph and assign
color $3$ to it. Thus, an odd $3$-edge-coloring for
$G^{\prime}=G\backslash\\{e^{\prime}\\}$ is obtained, and this shows
$s\in\mathcal{O}$.

Now, Claim 3 and Lemma 3.6 imply that $\text{Int}_{G-v}(B)\cap
N_{G}^{\prime\prime}(s)=\emptyset.$ ∎

We are now ready to make one final claim that will lead to the completion of
our proof. This claim will address that there is at least one end-block whose
order is at least $4$.

Claim 6. There is an end-block $B$ of $G-v$ with $v(B)\geq 4$.

###### Proof.

Firstly, an end-block $B$ cannot have exactly $1$ vertex by definition of a
cut vertex. As stated in Claims 3, 4, and 5, an end-block $B$ also cannot
contain exactly $3$ vertices since it is simple and every vertex in $B$ has an
odd degree. Suppose now an end-block of $G-v$ contains exactly $2$ vertices,
namely $u$ and $s$, where $u$ is an internal vertex and $s$ is a cut vertex of
$G-v$. By Claims 3, 4, and 5, we know $d_{G}(u)=3$, $d_{G}(s)\geq 3$ is odd,
and $|\mathcal{B}_{us}|=1$. Since $s$ is a cut vertex of $G-v$, it must be
adjacent to some other neighbor other than $u$ and $v$ via an edge $e$. Below,
we will show that $G^{\prime}=G\backslash\\{e\\}$ admits an odd $3$-edge-
coloring.

Note that the vertex $s$ is not a cut vertex in $G^{\prime}$ and it is also
not a cut vertex of $G^{\prime}-u$. In the graph $G^{\prime}-u$, since
$d_{G^{\prime}-u}(s)$ is odd, Lemma 2.4(a) implies that there exists a
spanning odd coforest $H$ such that $d_{\hat{H}}(s)=0$, where
$\hat{H}=(G^{\prime}-u)\backslash E(H)$. Since $d_{G^{\prime}-u}(v)$ is
positive and even, both $d_{H}(v)$ and $d_{\hat{H}}(v)$ are odd. We assign
color $3$ to $E(H)$, and give an odd $2$-edge-coloring to $E(\hat{H})$ with
colors $1$ and $2$. By Lemma 2.2, we can also ensure that all of
$E_{\hat{H}}(v)$ receives color $1$. Finally, we assign color $1$ to
$\mathcal{B}_{uv}\cup\\{us\\}$. This procedure results in an odd $3$-edge-
coloring for $G^{\prime}=G\backslash\\{e\\}$. ∎

End of the proof of Theorem 1.3. Let $B$ be an end-block of $G-v$ containing
at least $4$ vertices, and $s\in B$ be a cut vertex. Note that $d_{B}(w)\geq
3$, for $w\in Int_{G-v}(B)$. Let $G_{1}=G-v$. Hence, by applying Lemma 2.4,
$G_{1}$ admits a spanning odd coforest $F$, and therefore
$\hat{F}=G_{1}\backslash E(F)$ is a forest. We claim that $F$ contains all
edges in $B$. In other words, the edge set of $\hat{F}$ does not intersect
with the edge set of $B$. Suppose otherwise; then this intersection is again a
forest and therefore has a leaf vertex in $B-s$ (or called a pendant vertex).
It means there is a vertex $w\in\text{Int}_{G-v}(B)$ such that
$d_{\hat{F}}(w)=1$. However, this implies that $d_{F}(w)$ is even and
positive, which is absurd. The claim follows.

By the previous claims, $B-s$ is a simple connected graph with minimum degree
at least 2. Then $B-s$ contains a cycle $C$. Let $F^{\prime}=F\backslash E(C)$
and note that $F^{\prime}$ is a spanning odd coforest of $G_{1}\backslash
E(C)$. Let $e$ be an arbitrary edge of $C$, and let $P=C\backslash\\{e\\}$.
Recall that $V(P)\subseteq N^{\prime\prime}_{G}(v)$. We will prove that
$G\backslash\\{e\\}$ admits an odd 3-edge-coloring.

We assign color $3$ to $E(F^{\prime})$ and then apply Lemma 2.2 to give an odd
$2$-edge-coloring to the forest $\hat{F}$, using colors $1$ and $2$. Consider
any vertex $w\in(N_{G}^{\prime\prime}(v)-V(P))$. We extend the odd coloring to
the edges of $\mathcal{B}_{vw}$. If the edge set $E_{G_{1}}(w)$ has received
only color $3$, then the bouquet $\mathcal{B}_{vw}$ of two edges receives
color $1$ and color $2$, respectively. Otherwise, if the edge set
$E_{G_{1}}(w)$ has already received color $1$ (or $2$), we assign this color
also to $\mathcal{B}_{vw}$. The remaining uncolored edges are the edges of $P$
and the edges connecting $P$ and $v$. These form a graph $H$, which has
exactly the same structure as described in Lemma 3.9, leading to two possible
cases.

  1. Case $1$.

If both colors $1$ and $2$ appear an even number of times in the edge set
$\bigcup_{w\in(N_{G}^{\prime\prime}(v)-V(P))}\mathcal{B}_{vw}$, we use the
first method in Lemma 3.9 to assign colors to $E(H)$.

  2. Case $2$.

If both colors $1$ and $2$ appear an odd number of times in the edge set
$\bigcup_{w\in(N_{G}^{\prime\prime}(v)-V(P))}\mathcal{B}_{vw}$, we use the
second method in Lemma 3.9 to assign colors to $E(H)$.

In either case, we can obtain an odd $3$-edge-coloring for the graph
$G\backslash\\{e\\}$. ∎

##  5\. Proof of Theorem 1.6

This section is devoted to the proof of Theorem 1.6. The proof, conducted by
contradiction, begins with the consideration of a possible minimal counter-
example and employs the technique of induction. The main inductive step is
presented in the following proposition.

######  Proposition 5.1.

Let $G$ be a simple connected graph with $\min\text{ovl}(G)\geq 3$. Let $v\in
V(G)$ be an even vertex.

  1. (a)

If $v$ is a cut vertex of $G$, then one can find a connected component $C$ of
$G-v$ such that the graph $G^{\prime}=G-C$ also satisfies that
$\min\text{ovl}(G^{\prime})\geq 3$.

  2. (b)

If $v$ is not a cut vertex, then $G-v$ is not a block graph. Furthermore,
there is an end-block $B$ of $G-v$ containing a unique cut vertex $s$ of $G-v$
such that the graph $G^{\prime}=G-(B-s)$ satisfies that
$\min\text{ovl}(G^{\prime})\geq 3$.

###### Proof.

(a) If any connected component of $G-v$ has an odd order, then Lemma 3.10
implies that $\min\text{ovl}(G)\leq 2$, which contradicts our assumption.
Therefore, we can assume that all connected components of $G-v$ have an even
order. There are two cases to consider.

Case 1. For every connected component $C$ of $G-v$, the degree
$d_{G[V(C)\cup\\{v\\}]}(v)$ is odd.

In this case, since $d_{G}(v)$ is even, we conclude that there are an even
number of components, namely, $C_{1},\cdots,C_{2k}$. In the graph
$G[V(C_{1})\cup\\{v\\}]$, by Lemma 2.4(b), we can find a $V(C_{1})$-join
$H_{1}$ which is a coforest and satisfies $d_{\hat{H}_{1}}(v)=1$, where
$\hat{H}_{1}$ is the edge complement of $H_{1}$ in $G[V(C_{1})\cup\\{v\\}]$.
We assign color $3$ to $E(H_{1})$. Clearly, $\hat{H}_{1}$ is a forest. We can
then give an odd $2$-edge-coloring to $\hat{H}_{1}$ using colors $1$ and $2$,
ensuring that $E_{\hat{H}_{1}}(v)$ receives color $1$.

For each of the remaining connected components $C_{j}$, $j=2,\cdots,2k$, we
follow a similar process: we obtain a $V(C_{j})$-join $H_{j}$ for the graph
$G[V(C_{j})\cup\\{v\\}]$ and assign color $1$ to it. Let
$\hat{H}_{j}=G[V(C_{j})\cup\\{v\\}]\backslash E(H_{j})$ be the edge complement
of $H_{j}$ in $G[V(C_{j})\cup\\{v\\}]$. We then give an odd $2$-edge-coloring
to $\hat{H}_{j}$ using colors $2$ and $3$, such that $E_{\hat{H}_{j}}(v)$
obtains color 3.

It can be verified that the resulting coloring is an odd $3$-edge-coloring for
the graph $G$. Consequently, $\min\text{ovl}(G)=0$, which contradicts the
assumption.

Case 2. There is a connected component $C$ of $G-v$ such that
$d_{G[V(C)\cup\\{v\\}]}(v)$ is even.

Let $G^{\prime}=G-C$ and we can see that $d_{G^{\prime}}(v)$ is even. Suppose,
for contradiction, that $G^{\prime}$ has $\min\text{ovl}(G^{\prime})\leq 2$.
Let $\varphi$ be an odd $3$-edge-covering of $G^{\prime}$ such that
$\text{ovl}(\varphi)\leq 2$, and suppose color $3$ appears in
$E_{G^{\prime}}(v)$ for $\varphi$.

Note that $v$ is an internal vertex for the induced subgraph
$G[V(C)\cup\\{v\\}]$. Then, by Lemma 2.4(a), there exists a $V(C)$-join $H$
which is a coforest and contains the whole $E_{G[V(C)\cup\\{v\\}]}(v)$. In
other words, we can define $\hat{H}$ to be the edge complement of $H$ in
$G[V(C)\cup\\{v\\}]$, then $d_{\hat{H}}(v)=0$. We assign color $3$ to all
edges in $E(H)$ and give an odd $2$-edge-coloring for $\hat{H}$ using colors
$1$ and $2$. Clearly, this procedure extends $\varphi$ to an odd $3$-edge-
covering of $G$, with overlapping at most $2$, which is a contradiction. This
shows that $\min\text{ovl}(G^{\prime})\geq 3$.

(b) If $G-v$ contains no cut vertices, then Corollary 3.12 implies that
$\min\text{ovl}(G)\leq 2$, which is absurd. So we can assume $G-v$ admits cut
vertices. Let $B$ be an end-block of $G-v$, which contains a unique cut vertex
$s$ of $G-v$. Note that every vertex $w\in B-s$ is an internal vertex of
$G-v$. Therefore, Lemma 3.11 directly implies the following.

  1. (1)

$v$ is adjacent to every vertex of $B-s$.

  2. (2)

every vertex $w$ in $B-s$ satisfies that $d_{G-v}(w)$ is even.

We next claim that $s$ is adjacent to every vertex of $B-s$.

Suppose otherwise. Then we can find vertices $w\in B$ such that $s$ is not
adjacent to $w$. Since $w$ has an odd degree, the neighbors of $w$ in $B-s$
can be listed as $\\{q_{1},\cdots,q_{2\ell}\\}$. Recall that $\mathcal{E}$
(respectively, $\mathcal{O}$) denotes the set of all even (respectively, odd)
vertices of $G$. By comparing parities, we see $|\mathcal{O}|$ is even,
implying that $|\mathcal{E}|$ is odd. We consider the even-sized vertex subset
$T=\mathcal{E}-\\{v\\}$ in the graph $G-(\\{v\\}\cup(B-s))$. Applying Lemma
2.3, we obtain a $T$-join $H$, which is also a forest. We give an odd
$2$-edge-coloring for $E(H)$ using colors 1 and 2. Then, we assign color $1$
to $wq_{j}$ and color $2$ to $vq_{j}$ for each $j=1,\cdots,2k$. For the
special edge $vw$, we assign both colors 1 and 2. We check that all the
uncolored edges of $G$ form an odd graph and then assign color $3$ to them.
This defines an odd $3$-edge-covering $\varphi$, with $\text{ovl}(\varphi)=2$,
which is a contradiction. Thus, the claim is established.

Now, in the graph $G^{\prime}=G-(B-s)$, we suppose, for contradiction, that it
admits an odd $3$-edge-covering $\psi$ with $\text{ovl}(\psi)\leq 2$. Since
the induced subgraph $B-s$ is an odd graph, it must have even order. Let
$V(B-s)=\\{v_{1},\cdots,v_{2k}\\}$. In the covering $\psi$, if a color appears
in both edge sets $E_{G^{\prime}}(v)$ and $E_{G^{\prime}}(s)$, let us say
color $1$, then we can extend the covering to an odd $3$-edge-covering
$\psi^{\prime}$ of $G$ with overlapping at most 2 by assigning color $1$ to
all the uncolored edges. Otherwise, without loss of generality, we can assume
that the edge set $E_{G^{\prime}}(s)$ contains color $1$ and does not contain
color $3$, while $E_{G^{\prime}}(v)$ contains color $3$ and does not contain
color $1$. Then, we assign color $3$ to all edges $vv_{j}$ and assign color
$1$ to all edges $sv_{j}$, for $j=1,2,\cdots,2k$, and then assign color $2$ to
all the edges in $B-s$. One can verify that this procedure extends $\psi$ to
an odd $3$-edge-covering $\psi^{\prime}$ of $G$ with overlapping at most $2$.
In either case, we have obtained a contradiction. ∎

###### Proof of Theorem 1.6.

With all the preparatory work completed as above, we proceed to prove the
theorem by contradiction. To do this, we select a simple connected graph $G$
as our example, satisfying $\min\text{ovl}(G)\geq 3$ and having the minimum
number of vertices. If $G$ contains at most $3$ vertices, then it contains at
most $3$ edges, and clearly $\min\text{ovl}(G)=0$, which is absurd.
Furthermore, since $v(G)=n$ is odd (as otherwise $\min\text{ovl}(G)=0$ by
Theorem 1.1), we have $v(G)\geq 5$. By comparing parities, there exists at
least one even vertex $v$. If $v$ is a cut vertex, we can apply Proposition
5.1 (a) to obtain an example $G^{\prime}$ with $\min\text{ovl}(G^{\prime})\geq
3$ with $|G^{\prime}|\leq|G|-2$, which contradicts our choice of $G$. If $G-v$
is connected, then we apply Proposition 5.1 (b) to obtain an example
$G^{\prime}$ with $\min\text{ovl}(G^{\prime})\geq 3$ with
$|G^{\prime}|\leq|G|-2$, which again contradicts our choice of $G$. ∎

## References

  * [1] Borut Lužar, Mirko Petruševski, and Riste Škrekovski.  Odd edge coloring of graphs.  Ars Mathematica Contemporanea, 9(2), 2014.
  * [2] Tamás Mátrai.  Covering the edges of a graph by three odd subgraphs.  Journal of Graph Theory, 53(1):77–82, 2006.
  * [3] USR Murty and Adrian Bondy.  Graph theory (graduate texts in mathematics 244), 2008.
  * [4] Mirko Petruševski.  Odd 4-edge-colorability of graphs.  Journal of Graph Theory, 87(4):460–474, 2018.
  * [5] Mirko Petruševski and Riste Škrekovski.  Coverability of graph by three odd subgraphs.  Journal of Graph Theory, 92(3):304–321, 2019.
  * [6] Mirko Petruševski and Riste Škrekovski.  Odd decompositions and coverings of graphs.  European Journal of Combinatorics, 91:103225, 2021.
  * [7] Mirko Petruševski and Riste Škrekovski.  Odd edge-colorings of subdivisions of odd graphs.  Journal of Graph Theory, 104(3):585–610, 2023.
  * [8] László Pyber.  Covering the edges of a graph by.  In Sets, Graphs and Numbers, Colloquia Mathematica Societatis János Bolyai, volume 60, pages 583–610, 1991.
  * [9] Alexander Schrijver.  Combinatorial optimization.  preprint, page 58, 2002.