ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 10 (2016) 359-370 Odd edge-colorability of subcubic graphs* Risto Atanasov Department of Mathematics and Computer Science, Western Carolina University, 28723 Cullowhee, NC, USA Mirko Petrusevski Department of Mathematics and Informatics, Faculty of Mechanical Engineering, Sts. Cyril and Methodius University, 1000 Skopje, Republic of Macedonia Riste Skrekovski Faculty of Mathematics and Physics, University of Ljubljana, 1000 Ljubljana, Slovenia Faculty of Information Studies, 8000 Novo Mesto, Slovenia University of Primorska, FAMNIT, 6000 Koper, Slovenia Received 16 October 2015, accepted 21 January 2016, published online 1 March 2016 An edge-coloring of a graph G is said to be odd if for each vertex v of G and each color c, the vertex v either uses the color c an odd number of times or does not use it at all. The minimum number of colors needed for an odd edge-coloring of G is the odd chromatic index xO(G). These notions were introduced by Pyber in [7], who showed that 4 colors suffice for an odd edge-coloring of any simple graph. In this paper, we consider loopless subcubic graphs, and give a complete characterization in terms of the value of their odd chromatic index. Keywords: Subcubic graph, odd edge-coloring, odd chromatic index, odd edge-covering, T-join. Math. Subj. Class.: 05C15 1 Introduction 1.1 Terminology and notation Throughout the article we mainly follow the terminology and notation used in [1, 11]. A graph G = (V(G), E(G)) is always regarded as being finite, i.e. having a finite nonempty *This work is partially supported by ARRS Program P1-0383. E-mail addresses: ratanasov@email.wcu.edu (Risto Atanasov), mirko.petrushevski@gmail.com (Mirko Petrusevski), skrekovski@gmail.com (Riste Skrekovski) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 360 Ars Math. Contemp. 10 (2016) 255-268 set of vertices V(G) and a finite (possibly empty) set of edges E(G). An edge with identical ends is called a loop, and an edge with distinct ends a link. Two or more links with the same pair of ends are said to be parallel edges. The parameters n(G) = |V(G)| and m(G) = |E(G)| are called order and size of G, respectively. A graph of order 1 is said to be trivial, whereas a graph of size 0 empty. For every v e V(G), EG(v) denotes the set of edges incident to v, and the size of EG (v) (every loop being counted twice) is the degree of v in G, with notation dG (■v). The maximum (resp. minimum) vertex degree in G is denoted by A(G) (resp. ¿(G)). We speak of G as a subcubic graph whenever A(G) < 3. Each vertex v having an even (resp. odd) degree dG(v) is an even (resp. odd) vertex. In particular, if dG(v) equals 0 (resp. 1), we say that v is an isolated (resp. pendant) vertex of G. Any vertex of degree d is also called a d-vertex. A graph is even (resp. odd) whenever all its vertices are even (resp. odd). The set of neighboring vertices of v e V (G) is denoted by NG(v). For every u e NG(v), the edge set EG(u) n EG(v) is called the uv-bouquet in G, with notation Buv. The maximum size of a bouquet in G is its multiplicity. We say that G is a simple graph whenever it is loopless and of multiplicity at most 1. Whenever the underlying graph G is clear from the context, the edge-complement of a subgraph H is denoted by H, i.e. H = G - E(H). A co-forest in G is a subgraph whose edge-complement is a forest. Every maximal path whose interior consists entirely of 2-vertices (of G) is called an open thread; similarly, every cycle all of whose vertices except one are 2-vertices of G is a closed thread. For every connected graph G that is not a cycle, each of its 2-vertices belongs to a unique thread, either open or closed. 1.2 Odd edge-colorings and odd chromatic index Any mapping y : E(G) ^ S is referred to as an edge-coloring of G, and then S is called the color set of y. We say that y is a k-edge-coloring when |S| < k. Since the nature of the colors is irrelevant, it is conventional to use S = [k] := {1,2,..., k} whenever the color set is of size k. For each color c e S, Ec(G, y) denotes the color class of c, being the set of edges colored by c (i.e. Ec(G, y) = y-1(c)); whenever G and y are clear from the context, we denote the color class of c simply by Ec. Given an edge-coloring y and a vertex v of G, we say the color c appears at v if Ec n EG(v) = 0. Any decomposition {H1;..., Hk} of G can be interpreted as its k-edge-coloring for which the color classes are E(Hi),...,E (Hfc). An odd edge-coloring of a given graph G is an edge-coloring such that each nonempty color class induces an odd subgraph. In other words, at each vertex v, for any appearing color c the degree dG[Ec](v) is odd. Equivalently, an odd edge-coloring can be seen as a decomposition of G into (edge disjoint) odd subgraphs. Such decompositions represent a counterpart to decompositions into even subgraphs, which were mainly used while proving various flow problems (see e.g. [6, 9]). Historically speaking, as a topic in graph theory, decomposing into subgraphs of a particular kind started with the paper of Erdos et al. [2]. An odd edge-coloring of G using at most k colors is referred to as an odd k-edge-coloring, and then we say that G is odd k-edge-colorable. Whenever G is odd edge-colorable, the odd chromatic index xO(G) is defined to be the minimum integer k for which G is odd k-edge-colorable. It is obvious that a necessary and sufficient condition for odd edge-colorability of G is the absence of vertices incident only to loops. Apart from this, the presence of loops does not influence the existence nor changes the value of the index xO(G). Therefore, while studying these matters it is enough to confine to loopless graphs. R. Atanasov, M. Petrusevski and R. Skrekovski: Odd edge-colorability ofsubcubic graphs 361 Figure 1: A simple graph with odd chromatic index equal to 4. As a notion, odd edge-coloring was introduced by Pyber in his survey on graph coverings [7]. The mentioned work considers simple graphs and (among others) contains a proof of the following result. Theorem 1.1 (Pyber, 1991). For every simple graph G, it holds that xO(G) < 4. Pyber remarked that the upper bound is realized by the wheel on four spokes W4 (see Fig. 1). This upper bound of four colors does not apply to the class of all looplees graphs G. For instance, Fig. 2 depicts four graphs with the following characteristic property: each of their odd subgraphs is of order 2 and size 1, i.e. a copy of K2. Consequently, for each of them the odd chromatic index equals the size of the graph. Figure 2: Four Shannon triangles (the smallest one of each type). As defined in [4], a Shannon triangle is a loopless graph on three pairwise adjacent vertices. Observe that for any Shannon triangle, as a direct consequence of the handshake lemma, the edge set of every odd subgraph is fully contained in a single bouquet. Let p, q, r be the parities of the sizes of the bouquets of a Shannon triangle G in non-increasing order, with 2 (resp. 1) denoting that a bouquet consists of an even (resp. odd) number of parallel edges. Then G is a Shannon triangle of type (p, q, r), and it holds that xO(G) = p + q + r. The following result was proven in [4]. Theorem 1.2. For every connected loopless graph G, it holds that x'o(G) < 6. Equality is achieved if and only if G is a Shannon triangle of type (2,2,2). In this paper we study the odd chromatic index for the class of loopless subcubic graphs G. We shall prove that over that class of graphs holds maxG xO(G) = 4. Moreover, we will give a complete characterization of the loopless subcubic graphs in terms of the value of their odd chromatic index. In doing so, we will use methods such as eliminating characteristic subtrees and unicyclic subgraphs, or odd co-forests, developed in [3, 10, 12]. The rest of the article is divided into three sections. In the next one, as a preliminary, are collected several 'easy' results (most of them previously known). Section 3 is devoted to a derivation of our main result - a characterization of the loopless subcubic graphs G in 362 Ars Math. Contemp. 10 (2016) 255-268 terms of the value of x0(G). The final section briefly conveys some ideas on odd edge-coverability of loopless subcubic graphs. 2 Preliminary results We begin by recalling the definition of a T-join. For a graph G, let T be an even-sized subset of V(G). Following [1], a spanning subgraph H of G is said to be a T-join if dH(v) is odd for all v e T and even for all v e V(G) \ T. For example, if P is an x-y path in G, the spanning subgraph of G with edge set E(P) is an {x, y}-join. Observe that the symmetric difference of a T-join and an S-join is a T A S-join. With the use of this simple fact and the mentioned example, it can be readily deduced (see [8]) that for any connected graph G and any even-sized subset T of V(G), there exists a T-join of G. Note also that by taking S = 0 we infer that the symmetric difference of a T-join and a spanning even subgraph is again a T-join. In particular, removal (resp. addition) of the edges of an edge-disjoint cycle from (resp. to) a T-join, furnishes a T-join. Thus, whenever a T-join of G exists, there also exists such a forest (resp. co-forest). The above discussion yields the following conclusion. Lemma 2.1. Given a connected graph G of even order, there exists an odd co-forest in G. The next lemma originally appears in [7]. For a proof we refer the reader to [4]. Lemma 2.2. If F is a forest, then x0(F) < 2. With the use of Lemmas 2.1 and 2.2, it can be easily shown that every connected graph of even order is odd 3-edge-colorable. Proposition 2.3. For every connected graph G of even order, it holds that x'0 (G) < 3. Proof. There exists an odd co-forest H in G. Take an odd edge-coloring of H with the color set {1,2} and extend it to E(G) by coloring E(H) with 3. Note that we have thus constructed an odd 3-edge-coloring of G. □ Corollary 2.4. Let v be a 2-vertex in a connected graph G of odd order. Then G admits a 3-edge-coloring that is nearly odd with the only exception being that EG(v) is monochromatic. Proof. Suppress the vertex v, i.e. remove it and then add an edge e with ends in NG(v) (the edge e is either a link or a loop depending on whether NG (v) is of size 1 or 2). Denote the obtained graph by H. Since H is connected and of even order, the previous proposition assures its odd 3-edge-colorability. Apply such an edge-coloring to H, and then 'reinstate' the vertex v on the edge e. We thus regain the graph G with a required edge-coloring. □ 3 Odd edge-colorability As already mentioned, throughout this section we consider loopless subcubic graphs. We begin by showing that four colors suffice for an odd edge-coloring of any such graph. Proposition 3.1. If G is a loopless subcubic graph, then x0(G) < 4. R. Atanasov, M. Petrusevski and R. Skrekovski: Odd edge-colorability ofsubcubic graphs 363 Proof. We may assume that G is connected and non-trivial. Moreover, by Proposition 2.3 we may assume that n(G) is odd. In case ¿(G) = 1 it is easily shown that xO(G) < 3. Indeed, say v is one of its pendant vertices. Since the graph G - v is connected and of even order, by Lemma 2.1 there exists an odd co-forest K in G - v. Let us denote its edge-complement in G by F, i.e. F = G - E(K). Then {K, F} is a decomposition of G into an odd subgraph K and a forest F. By coloring E(K) with 1, and applying to F an odd 2-edge-coloring with the color set {2,3}, we furnish an odd 3-edge-coloring of G. Henceforth we assume that ¿(G) = 2. Let v be one of its non-cut vertices. Either dG(v) = 2 or dG(v) = 3. We study first the case when dG(v) = 2 (see Fig. 3). G-v G-v Figure 3: The two possibilities when dG (v) = 2. v v f e Let EG(v) = {e, f}. By Lemma 2.1, consider a decomposition {K, F} of G - v consisting of an odd subgraph K and a forest F. Then the graph F + e is also a forest. Color E(K) with 1, the edge f by 2, and combine with an odd edge-coloring of F + e with the color set {3,4}. This confirms that G is odd 4-edge-colorable. G - v Figure 4: The only possibility when dG (v) = 3. Now we study the case when dG (v) = 3 (see Fig. 4). Denote by u the neighbor of v for which the uv-bouquet is of size 2. Clearly, u is a pendant vertex of G - v. Select an odd co-forest K in G - v. Observe that in its edge-complement K (taken in G - v), the vertex u is isolated. Color E(K) with 1; apply to the forest K an odd edge-coloring with the color set {2, 3}; color the bouquet Buv with 2 and 3; finally, color the remaining non-colored edge (incident to v) by 4. This gives an odd 4-edge-coloring of G. □ The established upper bound (of four colors) for the odd chromatic index of any loop-less subcubic graph is sharp. For example, consider the smallest Shannon triangle G of type (2,1,1) (the second of the graphs depicted in Fig. 2). As already observed in the introduction, xO(G) = 4. Note that this particular G can be obtained from a cubic bipartite v u 364 Ars Math. Contemp. 10 (2016) 255-268 graph (of order 2) by a single edge subdivision. As it turns out, every subcubic graph obtainable in this manner requires four colors for an odd edge-coloring. On the other hand, for any other connected loopless graph three colors suffice. In order to prove this assertion we will use the following lemma. Lemma 3.2. Let G be a connected graph having at least two 2-vertices. Then there exists a tree T in G that satisfies the following two conditions: (i) every 2-vertex of G belongs to V(T), (ii) every pendant vertex of T is a 2-vertex of G. Proof. We argue by induction on the number k of 2-vertices in G. In case k = 2, we merely take T to be a path in G connecting the only two 2-vertices. Assume that k > 2 and let the statement be true whenever the number of 2-vertices is less than k. Suppress a 2-vertex v of G, i.e. remove v and add a new edge e between its neighbors; denote the obtained graph by G'. The inductive hypothesis provides us with a tree T' satisfying the conditions (i) and (ii) for G'. If e G E(T'), then by reversing the suppression, i.e. by subdividing e, we arrive at the desired tree. Otherwise, T' is a subtree of G - v. If that is the case, then let P be a v-V(T') path in G and set T = P U T'. Note that T is a tree in G for which both (i) and (ii) hold. □ Proposition 3.3. For any connected loopless subcubic graph G, the following two statements are equivalent: (i) xO(G) = 4; (ii) G is obtainable from a cubic bipartite graph by a single edge subdivision. Proof. (i) ^ (ii): Let G be a connected loopless subcubic graph that cannot be obtained from a cubic bipartite graph by a single edge subdivision. We shall prove that xO(G) < 3. As in the proof of Proposition 3.1, we may assume that n(G) is odd and ¿(G) = 2. There are two cases to be considered. Case 1: G has at least two 2-vertices. Let T be a tree in G as in Lemma 3.2. Note that for each non-isolated vertex u of its edge-complement T the degree df (u) is odd. Therefore, the combination of an odd 2-edge-coloring of T with the color set {1,2} and a monochromatic edge-coloring of T with the color 3 constitutes an odd 3-edge-coloring of G. Case 2: G has a unique 2-vertex. Denote this particular vertex by v. Assume first the existence of an odd cycle (i.e. a cycle of odd length) Co in G that does not pass through v. Since G is connected, there exists a nontrivial v-V(Co) path P. Let w be the other endpoint of P (besides v) and consider the subgraph G' = P U Co. Note that w is the only isolated vertex of G'; moreover, every other vertex of G' has an odd degree. Color the set E(G') with 3; use the color 1 for EG(w); color the remaining non-colored edges of P and Co alternately by 1 and 2 such that the obtained edge-coloring of G' fails to be proper only at w (such a 2-edge-coloring of G' is possible because Co is an odd cycle). This completes an odd 3-edge-coloring of G. Assume now that such an odd cycle does not exist in G, meaning that every cycle avoiding v is even. We claim that there exists an even cycle Ce passing through v. To prove this, we argue as follows. Suppress the vertex v, and let e be the new edge. The obtained graph G* is cubic (since v is the only 2-vertex of G and ¿(G) = 2), which further R. Atanasov, M. Petrusevski and R. Skrekovski: Odd edge-colorability ofsubcubic graphs 365 implies that G* is not bipartite (otherwise, G would be obtainable from the cubic bipartite graph G* by a single edge subdivision). Consider an odd cycle C* of G*. By our current assumption, C* is not a cycle in G, which implies that e G E(C*). Therefore, v U V(C*) constitutes the vertex set of an even cycle Ce passing through v. Once the existence of Ce is established, we can construct an odd 3-edge-coloring of G as follows: take a proper 2-edge-coloring of Ce with the color set {1, 2}; then color the edge set of Ce with 3. (ii) ^ (i): Let G be obtainable from a cubic bipartite graph by a single edge subdivision. We shall show that xO(G) = 4. Denote by v the unique 2-vertex of G, and let G' be the graph obtained from G by suppressing v. Since G' is bipartite, there exists a partition X,Y of V(G') such that E(G') = E(X,Y). By Proposition 3.1, xO(G) < 4. Suppose this inequality is strict, i.e. suppose there exists an odd 3-edge-coloring of G with the color set {1,2,3}. Without loss of generality, we may assume that the v-X edge is colored by 1, whereas the v-Y edge is colored by 2. Let xi; x2, x3, xi23 be respectively the number of vertices u from X such that EG(u) is colored entirely with 1, entirely with 2, entirely with 3, or by all the three colors 1, 2, 3. Analogously, we employ notation yi; y2, y3, yi23 for the sizes of the respective subsets of Y. By double counting the color class Ei, we derive the equality 3xi + xi23 = 1 + 3yi + yi23 . (3.1) Reasoning similarly for the class E2, we deduce 1 + 3x2 + xi23 = 3y2 + yi23 . (3.2) Let us now consider the difference xi23 - yi23. From (3.1) it follows that xi23 - yi23 = 1(mod3). On the other hand, (3.2) yields xi23 - yi23 = -1(mod3). This is the desired contradiction. □ It is a trivial task to characterize the connected loopless subcubic graphs G that are odd 1-edge-colorable. Namely, xO(G) =0 if and only if G is Ki, whereas xO(G) = 1 precisely when G is odd. We proceed to characterize odd 2-edge-colorability. Proposition 3.4. If G is a connected loopless subcubic graph, then the following two statements are equivalent: (i) xO(G) < 2; (ii) for every cycle C of G, the set {v G V(C) : dG(v) = 2} is even-sized. Proof. (i) ^ (ii): Assume (i) and apply to G an odd 2-edge-coloring. Consider an arbitrary cycle C of G. Note that for every v G V(C) the edge set EC(v) is either monochromatic (when dG(v) = 3) or dichromatic (when dG(v) = 2). This clearly implies that the set {v G V(C) : dG(v) = 2} is even-sized. (ii) ^ (i): Assume that (ii) holds. In case G is a cycle, it is readily seen that (i) follows. Henceforth, we prove that (i) holds when G is not a cycle. For each pair x, y of non-even vertices of G consider an arbitrary x-y walk W, and count the number of traversed 2-vertices, i.e. count the 2-vertices of G appearing (possibly with repetition) in the interior of W. We claim that the parity of this number is an invariant of the unordered pair x, y, i.e. does not dependent on the choice of W. Indeed, if we suppose the existence of an x-y walk W' which presents a counterexample combined with W, then the symmetric 366 Ars Math. Contemp. 10 (2016) 359-370 difference E(W) © E(W') must contain the edge set of a cycle C of G for which the set {v e V(C) : dG (v) = 2} is odd-sized. Let us employ notation x ~ y (resp. x « y) whenever the parity of the considered number is odd (resp. even). Seen as binary relations on the set on non-even vertices, both ~ and « are symmetric. Moreover, by concatenating suitable walks, one readily deduces that « is an equivalence relation, whereas ~ is non-transitive (i.e. x ~ y & y ~ z ^ x « z). This means that there are at most two equivalence classes of In other words, the set of non-even vertices of G can be written as a disjoint union of two (possibly empty) subsets A, B such that x ~ y holds if and only if x and y belong to distinct subsets. Note that there is no A-B edge in G. For each u e A color EG(u) with 1; similarly, for each u e B color Eg (u) with 2. This gives a partial edge-coloring of G such that any non-colored edge is incident to a 2-vertex. Apply the following procedure: as long as there exists a 2-vertex, say v, with EG(v) not fully colored, consider the unique thread H that contains v. Two edges of H are already colored, and this pre-coloring extends to an edge-coloring of H with the color set {1,2} that is proper at each 2-vertex belonging to V(H). (In case the two pre-colored edges received the same color then the length of H is odd; on the other hand, if they are of different colors, then the length is even.) This eventually completes an odd 2-edge-coloring of G. □ Since all the threads of a given connected loopless subcubic graph G can be detected in linear time, it is linearly decidable whether the set on non-even vertices of G admits a partition into two (possibly empty) subsets A and B as in the proof of the implication (ii) ^ (i). Thus, it can be checked in linear time whether x'o(G) < 2. Moreover, the proof of (ii) ^ (i) suggests the following constructive characterization of odd 2-edge-colorability. Corollary 3.5. Every connected loopless subcubic graph G satisfying xO(G) < 2 is either an even cycle or can be obtained from a connected odd subcubic graph Go (loops allowed) in the following manner: 1. split V(Go) arbitrarily into two (possibly empty) subsets A and B; 2. subdivide an odd number of times each edge from E(A, B); 3. subdivide an even non-zero number of times each loop from E(Go); 4. subdivide an even (possibly zero) number of times each link whose endvertices belong to the same set from the pair A, B. To summarize this section, we state the promised characterization of all connected loop-less subcubic graphs in terms of their odd chromatic index. Theorem 3.6. Let G be a connected loopless subcubic graph. Then if G is empty; if G is odd; if G has 2-vertices, with an even number of them on each cycle; if G is obtained from a cubic bipartite graph by a single edge subdivision ; otherwise. x'o(G) 3 R. Atanasov, M. Petrusevski and R. Skrekovski: Odd edge-colorability ofsubcubic graphs 367 The above comments on the algorithmic aspects of odd 2-edge-colorability, combined with the well-known fact that the decision problem whether a given graph is bipartite can be solved in polynomial time (by using Breadth-First Search), assure that our characterization is good. Corollary 3.7. For any loopless subcubic graph G, the odd chromatic index xO(G) can be determined in polynomial time of n(G). 4 Odd edge-coverability In this section we present an application of Theorem 3.6 while briefly studying the odd edge-coverability of subcubic graphs, a related concept to odd edge-colorability. An edge-covering of a graph G is a family {Hi,..., Hk} of subgraphs such that Ui=1 E(H) = E(G). Any edge-covering of G can be interpreted as a 'generalized edge-coloring', i.e. a mapping f * : E(G) ^ P*([k]) assigning to each edge of G a nonempty subset of the set of colors {1,..., k}. In other words, we pass from edge-colorings to edge-coverings by allowing more than one color per edge. In the context of an edge-covering f *, the color class Ec of any color c G [k] consists of the edges e G E(G) for which c G f * (e). If each non-empty color class induces an odd subgraph, then we speak of an odd edge-covering of G. More verbosely, we say that G is odd k-edge-coverable whenever it admits an odd edge-covering with at most k colors. The minimum size (i.e. minimum number of colors) of an odd edge-covering of G is denoted by covo(G). Similar to odd edge-colorability, a given graph G is odd edge-coverable if and only if there are no vertices incident only to loops, and apart from this, the presence of loops does not influence the existence nor changes the value of covo(G). Therefore, any study of odd edge-coverability should be restricted to loopless graphs. Since every odd edge-coloring of G is also an odd edge-covering, it holds that cov0(G) < xO(G). (4.1) As a notion, odd edge-covering was introduced in [5]. The scope of the mentioned work are all simple graphs, and the following result is proven. Theorem 4.1 (Mitrai, 2006). For every simple graph G, it holds that covo(G) < 3. In this section we consider the possible values of the index covo(G) taken over all connected loopless subcubic graphs G. When G is the smallest Shannon triangle of type (2,1,1) (the second graph in Fig. 2), the handshake lemma readily implies that covo(G) = 4; indeed, for every graph G of order n(G) = 3 the equality covo(G) = xO(G) holds. We shall prove that this is the only exception to odd 3-edge-coverability of connected loopless subcubic graphs. For this we should note that, according to (4.1) and Theorem 3.6, any exception must be obtainable from a cubic bipartite graph by a single edge subdivision. Thus, it is enough to consider the odd 3-edge-coverability of that particular class of graphs. Proposition 4.2. Apart from the smallest Shannon triangle of type (2,1,1), every other connected loopless subcubic graph is odd 3-edge-coverable. Proof. Suppose the opposite, i.e. let G present a counterexample. Hence, G can be obtained from a cubic bipartite graph H by a single edge subdivision. Say the subdivided edge e G E(H) has endpoints x and y, and let v be the introduced 2-vertex. Denote by ex and ey the respective 'parts' of e in G (see Fig. 5). 368 Ars Math. Contemp. 10 (2016) 359-370 v —^^ y H G Figure 5: The graphs H and G. (The possibility of another xy-edge in H, i.e. an xy-edge in G, is not excluded.) Let Bxy be the xy-bouquet of H. Since H is a cubic graph and G is not the smallest Shannon triangle of type (2,1,1), the size of Bxy is either 1 or 2. We claim the latter. To confirm this, we argue by contradiction. Suppose the opposite, i.e. let x and y be non-adjacent in G. First we show that the graph G - v is connected. Otherwise, it must consist of two components Hx and Hy, containing x and y, respectively. Moreover, since the only even vertex of the graph Hx (resp. Hy) is the 2-vertex x (resp. y), the handshake lemma implies that both n(Hx) and n(Hy) are odd. By Corollary 2.4, there exists an edge-coloring ^>x (resp. ) of Hx (resp. Hy) with the color set {1,2,3} that is nearly odd, the only exception being that the edge set EHx (x) is colored with 1 (resp. the edge set EHy (y) is colored with 2). Apply ^>x U ^>y, and then color ex by 1 and ey by 2. We thus obtain an odd 3-edge-coloring of G, a contradiction. This confirms that G - v is indeed connected. Denote by P ashortest x-y path in G-v,andsay x, u1;... ,uk_i,y are the consecutive vertices met on a traversal of P. Since H is bipartite with x and y belonging to different partite sets, the length k is an odd integer greater than 2. Suppose that NG_v(x) = {u1}, i.e. let the bouquet Bxui be of size 2. We can then apply to G the following edge-covering with the color set {1, 2, 3}: color ex with 1; for ey use both 2 and 3; color Bxui with 1; for the u1M2-edge of P use both 1 and 3; color the rest of E(G) with 3. This clearly implies covo(G) < 3, a contradiction. Therefore, it must be that, besides u1, there exists another neighbor of x in G - v; let us denote this particular vertex by u. The choice of P assures u