Reza Naserasr

Weiqiang Yu

On the packing number of antibalanced signed simple planar graphs of negative girth at least 5

Keywords: signed graph, packing number, planar graphs

The packing number of a signed graph (G, σ), denoted ρ(G, σ), is the maximum number of signatures σ 1 , σ 2 , • • • , σ l such that each σ i is switching equivalent to σ and the sets of negative edges E - σ i of (G, σ i ) are pairwise disjoint. A signed graph packs if its packing number is equal to its negative girth. A reformulation of some wellknown conjecture in extension of the 4-color theorem is that every antibalanced signed planar graph and every signed bipartite planar graph packs. On this class of signed planar graph the case when negative girth is 3 is equivalent to the 4-color theorem. For negative girth 4 and 5, based on the dual language of packing T-joins, a proof is claimed by B. Guenin in 2002, but never published. Based on this unpublished work, and using the language of packing T-joins, proofs for girth 6, 7, and 8 are published. We have recently provided a direct proof for girth 4 and in this work extend the technique to prove the case of girth 5.

Introduction

A graph G is called planar if it can be embedded in plane in such a way that its edges intersect only at their endpoints. A signed graph (G, σ) is a graph together with a signature σ which assigns a sign (i.e., + or -) to each edge of G. We denote by E - σ the set of negative edges of a signed graph (G, σ). Given a graph G, the signed graph (G, -) (respectively, (G, +)) is the signed graph where all edges are negative (positive). One of the key notions in the study of signed graphs is the concept of switching. A switching of a signed graph (G, σ) at a vertex v is the operation of multiplying the signs of all edges incident to v by a -. When e is a loop on a vertex v, then v will be viewed as the two ends of e, which means switching does not affect the sign of a loop. A switching of (G, σ) is a collection of switchings at each of the elements of a given set X of vertices. That is equivalent to switching the signs of all edges in the edge cut (X, V \ X). Two signatures σ 1 and σ 2 on a graph G are said to be equivalent if one can be obtained from the other by a switching, in this case we say (G, σ 1 ) is switching equivalent to (G, σ 2 ).

Given a signed graph (G, σ) and a signature σ i equivalent to σ, when there is no ambiguity, we may write E - i in place of E - σ i . It is easily observed that (G, σ 1 ) and (G, σ 2 ) are switching equivalent if and only if the symmetric difference E - 1 E - 2 is an edge cut of G. The sign of a structure in a signed graph (G, σ) is the product of the signs of the edges in the given structure, counting multiplicity. Note that the signs of cycles are invariant under a switching operation and they determine some crucial properties of a signed graph. If every cycle in a signed graph (G, σ) is positive, then (G, σ) is said to be balanced. A signed graph (G, σ) is said to be antibalanced if (G, -σ) is balanced.

Harary was first to show that a signed graph is balanced if it is equivalent to (G, +). An extension of this is the following result of Zaslavsky which shows that the set of negative cycles of a signed graphs uniquely determines the equivalence class of signatures: Theorem 1. [START_REF] Zaslavsky | Signed graphs[END_REF] Given two signatures σ 1 and σ 2 on a graph G, they are equivalent if and only if (G, σ 1 ) and (G, σ 2 ) have the same set of negative cycles.

Given a signed graph (G, σ) and an element ij ∈ Z 2 2 , we define g ij (G, σ) to be the length of the shortest closed walk W whose number of negative edges modulo 2 is i and whose length modulo 2 is j. When there exists no such a closed walk, we define g ij (G, σ) = ∞. Furthermore, the length of a shortest negative closed walk will be denoted by g -(G, σ) (i.e., g -(G, σ) = min{g 10 (G, σ), g 11 (G, σ)}). Given ij ∈ Z 2 2 , ij = 00, the class G ij of signed graphs is defined as follows:

G ij = {(G, σ) | g i j (G, σ) = ∞ for i j ∈ Z 2
2 -00, i j = ij}. Hence, G 01 is the class of signed graphs (G, σ) which can be switched to (G, +) and G 11 is the class of signed graphs (G, σ) which can be switched to (G, -). The class G 10 is the class of signed bipartite graphs.

Given signed graphs (G, σ) and (H, π), a homomorphism of (G, σ) to (H, π) is a mapping ϕ of the vertices and edges of G to the vertices and edges of H, respectively, such that adjacencies, incidences and signs of closed walks are preserved. When there exists such a homomorphism, we write (G, σ) → (H, π). The definition of homomorphisms of signed graphs implies the following no-homomorphism lemma:

Lemma 2. If (G, σ) → (H, π), then g ij (G, σ) ≥ g ij (H, π) for every ij ∈ Z 2 2 .
The packing number of a signed graph (G, σ), denoted ρ(G, σ), is the maximum number of signatures σ 1 , σ 2 , • • • , σ l such that each σ i is switching equivalent to σ and the sets E - i are pairwise disjoint. The signed projective cube of dimension d, denoted SPC d , is a signed graph with the vertex set Z d 2 , two vertices of SPC d being adjacent by a positive edge if they are at hamming distance 1 and by a negative edge if they are at hamming distance d. Let SPC o d be the signed graph obtained from SPC d by adding a positive loop to each of its vertices. A relation between packing numbers and homomorphisms observed in [START_REF] Naserasr | Packing signatures in signed graphs[END_REF] is as follows: Theorem 3. [START_REF] Naserasr | Packing signatures in signed graphs[END_REF] Given a non-negative integer d, for a signed graph (G, σ), we have ρ(G, σ) ≥ d + 1 if and only if (G, σ) → SPC o d .

Combined with the main result of [START_REF] Brewster | The complexity of signed graph and edge-coloured graph homomorphisms[END_REF], this implies that given an integer k ≥ 2, for the general class of signed graphs the problem of deciding if p(G, σ) ≥ k is an NP-complete problem. In contrast the following relaxation of the problem is easily tractable. Given signed graph (G, σ) and a set σ 1 , . . . , σ r of signatures each equivalent to σ can we find an equivalent signature σ which has no common negative edge with any of (G, σ i )'s? The following easy theorem provides an efficient algorithm for this question: Theorem 4. Given signed graph (G, σ) and a set σ 1 , . . . , σ r of signatures each equivalent to σ, there exists an equivalent signature σ which has no common negative edge with any of (G, σ i )'s if and only if the set ∪ r i=1 E - i induces a bipartite graph. Given a signed graph (G, σ), since every signature must assign at least one negative sign to the edges of a negative cycle, we know that:

ρ(G, σ) ≤ g -(G, σ). We say (G, σ) packs if ρ(G, σ) = g -(G, σ). It is straightforward to verify that ρ(K 4 , -) = g -(K 4 , -) = 3, so (K 4 , -)
packs. Note that (K 5 , -) is the smallest signed simple graph whose packing number is 1, in particular (K 5 , -) does not pack. Meanwhile, the smallest signed multigraph which does not pack has only three vertices, that is the signed graph K 2 3 as depicted in Figure 1.

Figure 1: ρ(K 2 3 ) = 1, g -(K 2 3 ) = 2
Restated in the language of packing signatures, a result of Gan and Johnson [START_REF] Gan | Four problems on graphs with excluded minors[END_REF] in 1989 claimed that if a signed graph (G, σ) has no K 2 3 -minor, then it packs. This result applies to signed graphs allowing multi-edges and loops. When restricted on signed simple graphs, the story becomes much more complicated, but it is still expected that in some sense (K 5 , -) is the minor-minimal element among certain classes of signed simple graphs that do not pack. More precisely, the following conjecture is strongly related to some of the central problems in graph theory and, in particular, to the four-color theorem and to several conjectures in extension of it. The restriction to the classes G 11 and G 10 of signed planar graphs is necessary. There exists a planar simple graph (thus negative girth 3) whose packing number is 1. This follows from a coloring result of [START_REF] Kardoš | On the 4-color theorem for signed graphs[END_REF], we refer to [START_REF] Naserasr | Packing signatures in signed graphs[END_REF] for more details.

However, one may expect that, while remaining in the class G 11 ∪ G 10 , the condition of planarity can be replaced with having no (K 5 , -).

The restriction of the conjecture to the subclass with negative girth 3 is equivalent to the four-color theorem. The restriction to the class with negative girth 4 is known to imply the four-color theorem and is proved using it, historical background provided next.

In the subclass of planar graphs the conjecture can restated using the dual notion of packing T -joins where T would be vertices of the dual that correspond to the negative faces of the planar embedding. The statement of the conjecture based on the notion packing T -join was first proposed by B. Guenin in early 2000's who then gave a proof of the next two cases. In our language that would be proving the conjecture for members of the class whose negative girth is 4 or 5. The T -join approach is extended in three follow up work which means that the conjecture is proved for the cases with negative girth at most 8. We note that proof for each case of girth condition relies on the proof for the earlier cases, thus dependent on the proof of the 4-color theorem. However, the work of Guenin remains unpublished and mostly not available.

An independent proof for the case of girth 4 is recently given in [START_REF] Naserasr | Packing signatures in signed graphs[END_REF]. This proof has extra advantage that works for any minor closed family that are 4-colorable. Thus, on the one hand it works for the larger family of K 5 -minor free graphs, and, on the other hand, it provides a proof without the use of the 4-color theorem for subclasses such as graphs of treewidth at most 3. In this work we build up on our method from [START_REF] Naserasr | Packing signatures in signed graphs[END_REF] to verify the case girth 5 of this conjecture. The main idea of the proof is presented in [START_REF] Naserasr | Packing signatures in signed graphs[END_REF]. We first provide a reformulation of the conjecture, then we do a double induction and use different statements for different directions of the induction. The restatement of the conjecture is based on the following definition.

Given a signed graph (G, σ) of negative girth k, a negative cycle C of it is said to be super negative if it has at most k -2 positive edges. The key property of a super negative cycle, relevant to this study, is in the following observation. Let σ be a signature equivalent to σ but disjoint from it, one can easily find such a signature using Theorem 4. Let G /σ be the graph obtained from G by contracting the negative edges of σ and (by little abuse of notation) let σ be the signature on G /σ where the negative edges of it are the images of the negative edges of (G, σ ). That (G /σ , σ ) is well defined because the two signatures do not share a negative edge. Now a negative cycle C in (G /σ , σ ) is of length less than or equal to k -2 if and only if it is the image of a super negative cycle of (G, σ). This is the key point in showing that the following is equivalent to Conjecture 5. We refer to [START_REF] Naserasr | Packing signatures in signed graphs[END_REF] for more details. Conjecture 6. Any signed planar graph in G 11 ∪G 10 admits an equivalent signature σ where (G, σ ) has no super negative cycle.

We shall note that the property of having no super negative cycle is a homomorphism property in the following sense: Suppose (H, π) is a signed graph where every negative cycle has at least l positive edges. If a signed graph (G, σ) maps to (H, π), then there is a signature σ equivalent to σ such that in (G, σ ) each negative cycle has at least l positive edges. One such choice for σ is by taking inverse image of π under the homomorphism of (G, σ) to (H, π).

This observation and Theorem 3 imply that given an integer k, a minimum counterexample (G, σ) of negative girth k to each of Conjecture 5 and Conjecture 6 must have no proper homomorphic image which satisfies all three conditions: It is of negative girth k, it is planar, and it is in G 11 ∪ G 10 . Then, combined with the folding lemma of [START_REF] Klostermeyer | 2 + )-coloring of planar graphs with large odd girth[END_REF] which applies to cases in G 11 and the folding lemma of [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF] that applies to cases in G 10 , we conclude that in every planar embedding of (G, σ) each face must be a negative k-cycle.

The rest of this paper is about proving the following theorem.

Theorem 7. For any antibalanced signed simple planar graph (G, σ) of negative girth at least 5, we have ρ(G, σ) ≥ 5.

Proof of Theorem 7

Let us start with the full picture of the proof. We are assuming that each planar graph in G 11 ∪ G 10 with negative give at most 4 packs. The case of negative girth 3 is equivalent to the 4-color theorem and the case of negative girth 4 is a stronger statement a proof of which can be found in [START_REF] Naserasr | Packing signatures in signed graphs[END_REF]. Let us take a planar graph (G, σ) in G 11 with negative girth at least 5. We want to prove that ρ(G, σ) ≥ 5. Let us suppose we can find a switching equivalent signature σ such that (G, σ ) has no super negative cycle. By Theorem 4, we can find a second equivalent signature σ such that (G, σ ) and (G, σ ) have no negative edge in common. We then contract all the negative edges in (G, σ ) and consider the negative edges of σ as a signature on this new graph. This would be a signed planar graph in G 10 whose negative cycles are of length at least 4. Applying the case of negative girth 4, we have four disjoint signatures on the contracted graphs. Together with σ we have a total of five signatures with no pair of them having a common negative edge.

So what remains to show is that (G, σ) admits an equivalent signature with no super negative cycle. At this point the second inductive step kicks in. We assume G is a smallest counterexample. That is to say: G is a planar graph in G 11 which has no loop and no triangle, it does not admit a packing of size five and among all such examples, it has (first) minimum number of vertices and (second) minimum number of edges. The order on the number of vertices together with the folding lemma implies that all faces are 5-cycles. The minimality of the number of edges means removing any edge e, the remaining signed graph must admit a 5-packing. Viewing each of these five signatures as a signature on G, equivalent to σ, we must have a super negative cycle. However, each such a cycle must include e. This would be enough to stablish a rich enough structure around vertices of degree 2 and 3 to apply discharging technique and get a contradiction with Euler's formula. Thus we split details of the proof to three parts: dealing with 2-vertices, 3-vertices and then discharging.

2-vertices

Let v be a vertex of degree 2 in G and let x and y be its two neighbours, furthermore, in the rest of this subsection e is the edge vx and e is the edge vy.

Let σ 1 , σ 2 , σ 3 , σ 4 , σ 5 be the five signatures equivalent to σ such that, when restricted on G -e, they have no common negative edge. Thus e is the only potentially common negative edge among some of these signatures. Each (G, σ i ) must contain a super negative cycle. If more than one, then we choose one and name it C i . Moreover we denote by P i the x -y path in C i that does not contain v. Furthermore, we assume σ i 's are minimal in the sense that there is no other signature on G -e equivalent to σ such that all its negative edges are also negative in σ i . Clearly replacing each signature with a minimal one does not affect the packing property. However, then we may have a set of edges each of which is positive in all five of (G -e, σ i ). Let E 6 be such set of edges of G -e. We proceed with a series of claims.

Claim 1. We have one of two:

• Either σ i (e) = σ i (e ) for each i, i = 1, 2, . . . , 5, in which case all the positive edges of each C i must be in E 6 .

• Or for exactly one of the five signatures, say σ 5 , we have σ i (e) = σ i (e ) in which case the positive edge of each P i in (G, σ i ), i = 1, 2, 3, 4, is a negative edge in (G, σ 5 ).

Proof. First we show that we cannot have two such signatures satisfying σ i (e) = σ i (e ). Suppose to the contrary that two of them, say σ 1 and σ 2 , assign the same sign to e and e . By switching at v, if necessary, in each of (G, σ 1 ) and (G, σ 2 ) we may assume that σ 1 (e) = σ 1 (e ) = + and σ 2 (e) = σ 2 (e ) = +. This implies that all the edges of P 1 are given a negative sign in (G, σ 1 ) and, similarly, all the edges of P 2 are given a negative sign in (G, σ 2 ), and thus a positive sign in (G, σ 1 ). Recall that, since each C i is an odd cycle, each P i is a path of odd length. Then the closed walk induced by P 1 ∪ P 2 , in (G, σ 1 ), and hence in (G, σ), is negative closed walk of even length. This contradicts the fact that (G, σ) ∈ G 11 .

Hence, and without loss of generality, we assume σ i (e) = σ i (e ) for i = 1, 2, 3, 4. Then for each i, i = 1, 2, 3, 4, the path P i has a unique positive edge in (G, σ i ). Let us name this edge e i . Then we first observe that e i cannot be negative in any of (G, σ j ), j = 1, 2, 3, 4 as otherwise, C i would be a positive cycle in (G, σ j ). If σ 5 (e) = σ 5 (e ), then for C i , i = 1, 2, 3, 4, to be negative in (G, σ 5 ) we have σ 5 (e i ) = + which implies the first case of the claim. If σ 5 (e) = σ 5 (e ), then for C i , i = 1, 2, 3, 4, to be negative in (G, σ 5 ) we must have σ 5 (e i ) =in which case we have the second part of the claim.

Note that one may change the sign of all edges in E 6 to negative in (G, σ 5 ). As (G -e, σ) is in G 11 , the resulting signature is also equivalent to σ. Thus we may assume that the second item of the claim is always the case at the cost of allowing σ 5 not to be minimal. Under this assumption, we may also assume that σ 5 (e) = σ 5 (e ) = +, as otherwise we may switch at v in (G, σ 5 ). This, in particular, means that for any super negative cycle C 5 , e and e are the only positive edges.

We should note that in choosing the super negative cycle C i of (G, σ i ) one may have more than one choice. Next we aim at showing that among the possible choices, at least one should have a fair number of high degree vertices. Recall that in our case of negative girth 5 a super negative cycle has either 2 or 0 positive edges. Thus if a super negative cycle has at least one positive edges, then it has precisely two positive edges. Claim 2. Assume σ is a minimal signature equivalent to σ such that every super negative cycle of (G, σ ) contains xvy with one positive edge and one negative edge, and that, moreover, the other positive edge is incident to either x or y. Then in one of the super negative cycles of (G, σ ) every vertex which is not incident to a positive edge is of degree at least 4 in G.

Proof. That σ is assumed to be a minimal signature implies, in particular, that no vertex is incident to only negative edges. Among all the signatures for which the conditions of Claim 2 hold but the conclusion does not, we take σ to be one where the number of super negative cycles of (G, σ ) is minimized. To get a contradiction we need to show that this number must be 0.

Suppose not and let C 1 , C 2 , . . . C r be the set of super negative cycles of (G, σ ) and assume that C 1 is a shortest one among these cycles. Since the condition does not hold, C 1 has a vertex z whose two neighbours on C 1 are connected to it by negative edges (with respect to the signature σ ) and d G (z) ≤ 3. Since not all edges incident to a vertex are negative, we must have d G (z) = 3 and that the third neighbour of z, say z , is adjacent to it with a positive edge. We first claim that z / ∈ {x, y}. Let P 1 be the x -z path in C 1 which does not include v and P 1 be the z -y path which does not include v. Observe that only one of P 1 and P 1 have a positive edge. We continue the proof assuming that P 1 has a positive edge, which then must be incident to y. The other case would be symmetric. If z = x, then P 1 together with xz induces a cycle with exactly one positive edge, depending on the parity of the length, that would either be a negative even cycle or a positive odd cycle both of which are forbidden in a member of G 11 . If z = y, then the cycle C 1 obtained from C 1 by replacing P 1 with the zy is also a super negative cycle of (G, σ 1 ) whose length is less than C 1 , contradicting the choice of C 1 .

Since z / ∈ {x, y}, and by our assumption that in every super negative cycle of (G, σ ) each positive edge is either incident to x or to y, we conclude that the edge zz does not belong to any super negative cycle of (G, σ ). We now consider the signature σ obtained from (G, σ ) by a switching at z. Then each super negative cycle of (G, σ ) is also a super negative cycle of (G, σ ) with the same signature. Thus (G, σ ) also satisfies the conditions of the claim, but it has less super negative cycles than (G, σ ), contradicting the choice of σ .

We note that each of σ 1 , σ 2 , σ 3 , and σ 4 satisfies the conditions of the Claim 2, and, therefore, the conclusion holds on these four signatures. For σ 5 this would depend on the possible cases of Claim 1. To take a better advantage of this case, we consider a signature σ 5 where the negative edges are those of σ 5 and the edges in E 6 . It is already mentioned that σ 5 is an equivalent signature. We have to following claim on (G, σ 5 ). Claim 3. In (G, σ 5 ) there exists a super negative cycle C in which all vertices, but possibly x, v and y, have degree at least 4 in G.

Proof. Observe that in (G, σ 5 ) the edges xv and vy are of the same sign. Thus if needed, by a switching at v we may assume they are both positive. This implies that in every super negative cycle of (G, σ 5 ) all edges not incident to v are negative. Let C 1 , C 2 , . . . , C r be the set of super negative cycles of (G, σ 5 ). If each of them has a vertex of degree 2 or 3, by switching at all those vertices we will get a signature with no super negative cycle, contradicting the minimality of the counterexample. The details that such switching does not create new super negative cycles and that each switching kills of the corresponding super negative cycle is similar to the previous claim. Claim 4. In each of (G, σ i ), i = 1, 2, 3, 4, one of the followings holds:

• Either x or y has a negative neighbour whose degree in G is at least 4.

• Each of x and y have a negative neighbour of degree 3.

Proof. Suppose to the contrary that one of them, say (G, σ 1 ) does not satisfy the claim. That means, for one of x and y, say y, all negative neighbours (possibly none) are of degree 2. Let (G, σ 1 ) be obtained from (G, σ 1 ) by switching at all negative neighbours of y. Since each of these vertices are of degree 2 and each is incident to at least one negative edge, the switching does not create a new super negative cycle. As y has no negative neighbour in (G, σ 1 ), the condition of Claim 2 holds for (G, σ 1 ). Thus (G, σ 1 ) has a super negative cycle C where each vertex not incident to a positive edge is of degree at least 4. Let x be the neighbour of x in C, x = v. Since C must be of length at least 5 and both positive edges are incident to y, both edges of C incident with x are negative and thus x has degree at least 4. Moreover, as x is not adjacent to y, and switchings were done only at neighbours of y, the sign of the edge xx is negative in (G, σ 1 ) as well. This means x is a negative neighbour of x whose degree is at least 4, thus the first case of the claim holds.

Claim 5. Suppose that u and v are two adjacent 2-vertices with u and v being the other neighbour, respectively. Then both u and v have degree at least 6 and have at least 5 4 + -neighbours.

Proof. By minimality of the counterexample we have signature packing σ 1 , σ 2 , σ 3 , σ 4 , σ 5 of (G -{u, v}, σ). Each of these signatures can be extended to G such that first of all (G, σ i ) is equivalent to (G, σ), secondly in each of them both uv and vv are positive, and thirdly, the condition that uv and vv having the same sign can be fulfilled by switching, if necessary, at v, u or both.

Since each (G, σ i ) has to have a super negative cycle, then uu must be a negative edge in all of them and this would be the only common negative edge between any pair of them. Each of these five signatures, however, satisfies the conditions of Claim 1, thus there is a super negative cycle C i in (G, σ i ) where vertices not incident to positive edges are 4 + -vertices. In C i the neighbour u i of u , u i = u, is not incident to a positive edge. Since u u i is negative only in (G, σ i ), the vertices u i are 5 distinct 4 + -neighbours of u . As u is also a distinct neighbour of u , it has total of at least six neighbours. The claim for v follows by symmetry. Claim 6. Suppose that u is a 2-vertex with u and v as neighbours and that v is 3-vertex with its two other neighbours being v 1 and v 2 . Then, first of all, u has at least four 4 + -neighbours. Secondly, among v 1 and v 2 either one has at least four 4 + -neighbours or together they have at least five 4 + -neighbours.

Proof. We consider induced signed subgraph by deleting the edge uu and as before define σ 1 , σ 2 , σ 3 , σ 4 to be four minimal signatures with no common negative edge and let σ 5 be the signature which assigns negative to the edges that are not negative in any of (G -uu , σ i ), i ≤ 4. As before, we consider σ i and σ 5 as signatures on G rather than G -uu , thus some of them have uu as (the only) common negative edge.

By our choice of σ 5 only the second case of Claim 1 can happen. Then if necessary, in (G, σ 5 ) we switch at u to get a (G, σ 5 ) where uu and uv are both positive, noting that each super negative cycle of (G, σ 5 ) is also a super negative cycle of (G, σ 5 ). As there must be at least one such cycle, and as there are already two positive edges, all other edges must be negative. That implies that, in particular, at least one of the two edges vv 1 and vv 2 is negative in (G, σ 5 ). We consider two cases depending on if only one is negative or both.

First assume the case that σ 5 (vv 1 ) = -and σ 5 (vv 2 ) = +. Since each edge beside uu is negative in only one of the signatures, we may assume σ i (vv 1 ) = -. Then for each j = i, in (G, σ i ) all the positive edges of each of the super negative cycle are incident to v, and, thus, by Claim 2 for j ≤ 4 and by Claim 3 in the case of j = 5 we have a super negative cycle in (G, σ j ) in which the neighbour of u distinct from u is of degree at least 4. We note moreover that the positive edges of any super negative cycle in (G, σ j ) are negative in σ 5 . This implies that vv 2 cannot be a positive edge in these cycles. Thus the second positive edge of any super negative cycle in (G, σ j ), j ≤ 4, j = i is vv 1 . Again using Claim 2 the neighbour of v 1 in each of these cycles must be at least of degree 4. Since that is the case for the super negative cycle of (G, σ 5 ) as well, v 1 must have at least four such neighbours. Now we consider the case that σ 5 (vv 1 ) = σ 5 (vv 2 ) = -. In this case then for all j's, j = 1, 2, . . . , 5 every super negative has two positive edges incident with v. Thus, first of all u will have at least five 4 + -neighbours, secondly, each of the signatures will imply a 4 +neighbour for either v 1 or for v 2 , giving a total of at least five such neighbours for the two of them.

3-vertices

Similar to the last subsection, let σ 1 , σ 2 , σ 3 , σ 4 , σ 5 be the five signatures equivalent to σ such that, when restricted on G -e, for a fixed edge e, each edge in G -e is negative in exactly one of these five signatures, and σ i 's are minimal for i = 1, 2, 3, 4. Thus e is the only potentially common negative edge among some of these signatures. As (G, σ i ) is a counterexample to Conjecture 6, each (G, σ i ) contains at least one super negative cycle, one of which is named C i . Claim 7. Every 4-cycle of G contains a vertex of degree at least 4.

Proof. Suppose not, let C = v 1 v 2 v 3 v 4 v 1 be a 4-cycle that all its vertices have degree at most 3. By the folding lemma, every face of G is of length 5. Thus C is not a facial cycle, hence it is a separating cycle. Moreover, since G is 2-connected, at least two of v 1 , v 2 , v 3 , v 4 have neighbours inside of C, and similarly at least two of them have neighbours outside. But since each v i is a 3 --vertex, it follows that they are all 3-vertices and that precisely two of them have neighbours inside and two of them have neighbours outside. By symmetry, we consider two case: (1) v 1 , v 2 have neighbours inside C, (2) v 1 , v 3 have neighbours inside C. In case (1), the path v 1 v 4 v 3 v 2 is part of a facial cycle inside C. As every facial cycle is a 5-cycle, there is a common neighbour of v 1 and v 2 . But that would make triangle with v 1 v 2 . In case [START_REF] Gan | Four problems on graphs with excluded minors[END_REF], considering the faces inside C formed by v 1 v 2 v 3 and v 1 v 4 v 3 , we conclude that the neighbours x, y of v 1 and v 3 inside C are themself adjacent and that the edge xy is part of both mentioned faces. That implies that x and y are adjacent 2-vertices. But we have already seen that for adjacent 2-vertices x, y their other neighbours must be of degree at least 6.

Claim 8. If C is a shortest super negative cycle, then C contains no chord.

Proof. Observe that a chord on a negative cycle creates one positive cycle and one negative cycle. Let C be a shortest super negative cycle with a chord e. Let C be the negative cycle created by C and e. We claim that C is a shorter super negative cycle, contradicting the choice of C. That C is negative is by our choice. That it is shorter is by the fact that there are no parallel edges and e is a chord of C. It remains to show that C is super negative, i.e. it has at most two positive edges. Since C has at most two positive edges in C ∪ {e} there are at most three positive edges. But as (G, σ) is switching equivalent to (G, -), every negative cycle (which is an odd cycle of G) has an even number of positive edges, thus C has at most two positive edges. Claim 9. Let v be a vertex of degree 3 in G and N (v) = {v 1 , v 2 , v 3 }, such that both v 2 and v 3 have degree 3. Let σ be a signature equivalent to σ such that every super negative cycle of (G, σ ) contains vv 1 , noting that such a signature exists by the minimality of (G, σ). If (G, σ ) has the extra property that every super negative cycle has two positive edges each of which is incident to at least one of v, v 2 or v 3 , then there exists a super negative cycle C σ such that every vertex not incident to a positive edge is of degree at least 4 in G.

Proof. Among all the signatures for which the conditions of Claim 9 hold but the conclusion does not, we take σ to be one where the number of super negative cycles of (G, σ ) is minimum. To get a contradiction we would like to show that this number must be 0. Let

N (v i ) = {v, x i , y i } for i = 2, 3.
Let C 1 , C 2 , . . . , C r be the set of super negative cycles of (G, σ ) and assume that C 1 is a shortest one among these cycles. Since the conclusion of the claim on (G, σ ) does not hold, C 1 has a vertex z whose two neighbours on C 1 are connected to it by negative edges (with respect to the signature σ ) and d G (z) ≤ 3. If all edges incident to z are negative, then we consider (G, σ ) obtained from (G, σ) by switching at z. We observe that super negative cycles of (G, σ ) are exactly those super negative cycles of (G, σ ) which do not contain z. Thus (G, σ ) also satisfies the conditions of the claim, but it has less super negative cycles than (G, σ ), contradicting the choice of σ .

Since both edges of C 1 incident to z are negative we must have d G (z) = 3 and that the third neighbour of z, say z , is adjacent to it with a positive edge. We claim zz belongs to some super negative cycle of (G, σ ). Suppose not. Let π be the signature obtained from (G, σ ) by switching at z. Then, first of all, there is still no super negative cycle in (G, π) containing zz , because for cycles containing this edge number of positive edges is the same in (G, σ ) and (G, π). Secondly, any super negative cycle of (G, σ ) containing z has two more positive edges in (G, π). Since we assume every super negative cycle of (G, σ ) has two positive edges, those containing z, in particular C 1 , are not super negative in (G, π). This contradicts with the number of super negative cycles of (G, σ ) being minimum. Thus zz is in a super negative cycle, say C i , 2 ≤ i ≤ r.

Next we claim that z / ∈ {v, v 1 }. We assume to contrary and first consider the case that z = v. Recall that vv 1 is an edge of C 1 . Between v 2 and v 3 , by symmetry, assume vv 3 ∈ C 1 . As edges of C 1 incident to z are negative we have σ (vv 1 ) = σ (vv 3 ) = -and since not all edges incident to z are negative we have σ (vv 2 ) = +. Since C 1 must have two positive edges, and they must be incident to v or v 2 or v 3 , the vertex v 2 should be on C 1 and moreover should be incident to a positive edge of C 1 . Noting that vv 2 is not an edge of C 1 , x 2 v 2 y 2 should be a part of C 1 . This implies that vv 2 is a chord of C 1 , contradicting Claim 8. Next we consider the case that z = v 1 . Recall that zz is a positive edge of a super negative cycle C i of (G, σ ) for some 2 ≤ i ≤ r. By the assumption, every positive edge of C i is incident to one of v, v 2 or v 3 . That means v 1 is adjacent to one of v, v 2 , v 3 with a positive edge. If vv 1 is a positive edge we have a digon otherwise we have a triangle. But either case contradicts the assumption on (G, σ).

Since zz must be a positive edge of the super negative cycle C i and since all such edges are incident to one of v, v 2 , v 3 we must have z ∈ {v 2 , v 3 , x 2 , y 2 , x 3 , y 3 }. By symmetries we consider only two possibilities of z = v 2 or z = x 2 . First let z = v 2 . If z = v, then C 1 contains the edge zz as a chord and we have contradiction with Claim 8. If z ∈ {x 2 , y 2 }, say z = y 2 , then σ (vv 2 ) = σ (v 2 x 2 ) = -, since vv 1 is also an edge of C 1 , vv 3 is not. As all positive edges are incident to v, v 2 or v 3 and since there are two such edges in C 1 , v 3 is a vertex of C 1 , but then again vv 3 is a chord contradicting Claim 8.

Finally assume z = x 2 and let N (x 2 ) = {v 2 , x 2 , x 2 }. If z = x 2 or z = x 2 , since zz belongs to a super negative cycle, positive edges of super negative cycles are incident to v, v 2 or v 3 and as G contains no triangle, z = v 3 , in which case vv 2 x 2 v 3 v is a 4-cycle which contains four 3-vertices, contradicting Claim 7. Therefore, we must have

z = v 2 , then σ (x 2 x 2 ) = σ (x 2 x 2 ) = -and x 2 x 2 x 2 is a part of C 1 . If vv 2 ∈ C 1 , then zz is again a chord of C 1 , which contradicts Claim 8. So vv 2 /
∈ C 1 , by symmetry we may write C 1 as v 1 vv 3 x 3 P 1 x 2 x 2 x 2 P 2 v 1 . If σ (vv 2 ) = -, then again vv 2 x 2 creates two cycles from C 1 one of which is negative. And this negative cycle has at most two positive edges, therefore is a super negative cycle and thus contains the edge vv 1 . By Claim 7, path v 1 vv 3 x 3 P 1 x 2 x 2 must have length at least 3, as otherwise together with v 2 we will have a 4-cycle all whose vertices are of degree 3. Replacing this path with vv 2 x 2 we find a shorter super negative cycle, contradicting the minimality of C 1 . Next let σ (vv 2 ) = +. By the assumption on C 1 , the fact that every cycle has even number of positive edges, and the fact that the edges of the path x 2 x 2 P 2 v 1 are all negative, we must have σ (vv 1 ) = -, as otherwise the cycle v 1 vv 2 x 2 x 2 P 2 v 1 has three positive edges. Since positive edges of C 1 must be incident to v, v 2 or v 3 , we have σ (vv 3 ) = σ (v 3 x 3 ) = +. Furthermore x 2 P 2 v 1 has an even number of edges since otherwise v 1 vv 2 x 2 x 2 P 2 v 1 is a shorter super negative cycle. Recall that zz is also in the super negative cycle C i . We consider the following two cases.

1. If vv 2 ∈ C i , then by our assumption vv 3 / ∈ C i , thus we may write C i as v 1 vv 2 x 2 P 3 v 1 , but then the cycle obtained from two paths from x 2 to v 1 of C 1 and C i forms a super negative cycle which does not contain vv 1 and contains no positive edge, a contradiction.

Otherwise vv

2 / ∈ C i , let C i = v 1 vv 3 y 3 P 3 x 2 x 2 v 2 y 2 P 4 v 1 .
But then the cycle vv 3 y 3 P 3 x 2 x 2 v 2 v contains exactly three positive edges, which never happens in (G, σ ).

Claim 10. Let v be a vertex of degree 3 in G and N (v) = {v 1 , v 2 , v 3 }, such that both v 2 and v 3 have degree 3. Then v 1 has at least two neighbours of degree at least 4.

Proof. Let G = G -vv 1 and σ 1 , σ 2 , σ 3 , σ 4 , σ 5 be the five signatures equivalent to σ such that, when restricted on G , they have no common negative edge. Thus vv 1 is the only potentially common negative edge among some of these signatures. Each (G, σ i ) must contain a super negative cycle using the edge vv 1 . If more than one, then we choose one and name it

C i . Let N (v i ) = {v, x i , y i } for i = 2, 3.
We first claim that among all these five signatures, there are at least two, in which, after switching at v, v 2 and v 3 (if necessary), we have the following: first of all in each of the four paths v 1 vv i x i and v 1 vv i y i , i = 2, 3, there are at least two positive edges, secondly, we do not create any new super negative cycle. First suppose vv 2 and vv 3 belong to the same signature, say E - 1 . Then in each of the other signatures, namely σ 2 , σ 3 , σ 4 and σ 5 , vv 2 and vv 3 are both positive. If vv 1 is also positive on at least two of σ 2 , σ 3 , σ 4 , σ 5 , then we are done. Assume in (G, σ 2 ), vv 1 is negative and both vv 2 and vv 3 are positive. Let σ 2 be obtained by switching at v. We first observe that every super negative cycle of (G, σ 2 ) is also a super negative cycle of (G, σ 2 ) because for i = 2, 3, if one of v i x i or v i y i is negative in σ 2 , then we switch at v i . Let σ 2 be the resulting signature. We observe that first of all no new super negative cycle is created, secondly in (G, σ 2 ) each of v 1 vv i x i and v 1 vv i y i has at least two positive edges. Next w.l.o.g. let vv 2 ∈ E - 1 and vv 3 ∈ E - 2 . Then in (G, σ i ), i = 1, 2, we could first switch at v (if necessary) to make vv 1 positive, since exactly one of vv 2 and vv 3 is positive, this switching will not create new super negative cycle. And then similarly we could either switch at v 2 or v 3 if necessary.

Therefore, we could find σ 1 and σ 2 obtained from σ 1 and σ 2 by switching at v, v 2 and v 3 , such that all the super negative cycles use the edge vv 1 and their two positive edges are either incident to v, v 2 or v 3 . Thus by Claim 9, their exists a super negative cycle C 1 of (G, σ 1 ) (similarly in (G, σ 2 )) such that every vertex not incident to a positive edge is of degree at least 4 in G. Let v 1 be another neighbour of

v 1 in C 1 , since v 1 is not adjacent to v 2 or v 3 , v 1 v 1 ∈ σ 1 . Then we claim that d(v 1 ) ≥ 4. If not, v 1 is incident to a positive edge of C 1 , which means v 1 ∈ {x 2 , y 2 , x 3 , y 3 }. Let v 1 = x 2 ,
since each super negative cycle has length at least 5 and C 1 uses the edge vv 1 , we have vv 2 / ∈ C 1 and x 2 v 3 / ∈ C 1 if it exists. Therefore both v 2 x 2 and v 2 y 2 belong to C 1 and v 2 x 2 is positive. Since vv 3 ∈ C 1 , by our claim above C 1 contains at least three positive edges, a contradiction. Therefore d(v 1 ) ≥ 4. Together with the same conclusion in (G, σ 2 ), we have that v 1 has at least two neighbours of degree at least 4.

Claim 11. Let u and v be two adjacent vertices of degree 3 in G. Assume σ is a signature equivalent to σ, such that every super negative cycle of (G, σ ) contains uv and contains two positive edges which are incident to either u or v. Then there exists a super negative cycle such that every vertex not incident to a positive edge is of degree at least 4 in G.

Proof. As in the proof of Claim 9 among all the signatures for which the conditions of Claim 11 hold but the conclusion does not, we take σ to be one where the number of super negative cycles of (G, σ ) is minimum, and, moreover, we take σ to be a minimal signature.

Let N (u) = {u 1 , u 2 } and N (v) = {v 1 , v 2 }.
Let C 1 , C 2 , . . . , C r be the super negative cycles of (G, σ ), and assume w.l.o.g. that |C 1 | ≤ |C j |, 2 ≤ j ≤ r. If the conclusion does not hold, then C 1 has a vertex z whose two neighbours on C 1 are connected to it by negative edges and d G (z) ≤ 3. Minimality of σ implies that d G (z) = 3 and that the third neighbour of z, say z , is adjacent to it with a positive edge. Furthermore, zz is in a super negative cycle, say C i , 2 ≤ i ≤ r, as otherwise by switching at z we have less super negative cycles.

As each of u and v is incident to a positive edge of C 1 , z / ∈ {u, v}. Considering the super negative cycle C i , zz is a positive edge, thus by our assumption one of the end point is u or v. As z / ∈ {u, v}, we have z ∈ {u, v} and hence z ∈ {u 1 , u 2 , v 1 , v 2 }. W.l.o.g. let z = u 1 and z = u. But then uu 1 is a chord of C 1 and we have a contradiction with Claim 8.

Claim 12. Let v 1 , v 2 , v 3 and v 4 be four vertices of degree 3, and σ be a signature equivalent to σ such that the following holds.

1.

v i is adjacent to v i+1 , i = 1, 2, 3. 2. σ (v 1 v 2 ) = -, σ (v 2 v 3 ) = σ (v 3 v 4 ) = +.
3. Each of v 2 and v 3 is incident to exactly two positive edges. 4. Either v 1 is incident to two positive edges or v 4 is incident to three positive edges. 5. Every super negative cycle of (G, σ ) contains the positive edge v 2 v 3 . 6. The other positive edge of any other super negative cycle must be incident to one of the v i (i ∈ {1, 2, 3, 4}).

Then there exists a super negative cycle of (G, σ ) such that every vertex not incident to a positive edge is of degree at least 4 in G. Proof. Again among all the signatures for which the conditions of Claim 12 hold but the conclusion does not, we take σ to be one where the number of super negative cycles of (G, σ ) is minimum. Let the other two neighbours of v i be x i , y i for i = 1, 4, and the third neighbour of v j be x j for j = 2, 3, as shown in Figure 2. Suppose to the contrary that C 1 , C 2 , . . . , C r are the set of super negative cycles of (G, σ ) and assume that C 1 is a shortest one among these cycles. Thus C 1 has a vertex z whose two neighbours on C 1 are connected to it by negative edges and d G (z) ≤ 3. It follows that d G (z) = 3 and that the third neighbour of z, say z , is a positive neighbour, moreover, zz is in a super negative cycle, say C l , 2 ≤ l ≤ r.

v 1 v 2 v 3 v 4 y 1 x 1 y 4 x 4 x 2 x 3
Since in (G, σ ) every super negative cycle contains v 2 v 3 as a positive edge, z / ∈ {v 2 , v 3 }. And since each positive edge of any super negative cycle is incident to some v i , we have z ∈ {v 1 , v 4 , x 1 , x 2 , x 3 , x 4 , y 1 , y 4 }. By symmetries we consider following possibilities.

1. z = v 1 . Since σ (v 1 v 2 ) = -, v 1 v 2 ∈ C 1 and at least one of v 1 x 1 , v 1 y 1 is negative.
By assumption v 4 is incident to three positive edges, and thus v 4 / ∈ C 1 . This contradicts with the fact that positive edges of every super negative are incident to v i .

2. z = v 4 . Since σ (v 3 v 4 ) = +, and edges in C 1 incident to z are both negative, we have that v 4 x 4 , v 4 y 4 ∈ C 1 and σ (v 4 x 4 ) = σ (v 4 y 4 ) = -, and hence z = v 3 . By the original assumption of the claim, σ (v 1 x 1 ) = σ (v 1 y 1 ) = +. Recall that every super negative cycle of (G, σ ) must contain v 2 v 3 . But any cycle that contains both v 2 v 3 and v 3 v 4 must contain at least one more positive edge. This is contradiction with the fact that zz is in a super negative cycle.

3. z = x 2 . Since σ (v 2 x 2 ) = + and v 2 x 2 / ∈ C 1 we must have v 1 v 2 ∈ C 1 . But then v 2 x 2 is a chord of C 1 which contradicts the Claim 8.

4. z = x 3 . Since the super negative cycle C l contains the positive edges zz and v 2 v 3 , it contains no other positive edges, in particular v 2 x 2 / ∈ C l . Thus v 1 ∈ C l . So each of v 1 and x 3 is incident with at least two negative edges, and they are not connected by a negative edge, since otherwise v 1 v 2 v 3 x 3 induces a negative 4-cycle. Recall that if a vertex of degree 3 is incident with at least two negative edges, then a switching at it may eliminate some super negative cycle, but will never create a new one. Thus if we switch at both v 1 and x 3 , then the remaining set of super negative cycles all must still contain the edge v 2 v 3 . But then in the new signature all edges incident to v 2 and v 3 are positive, which implies that every cycle containing v 2 v 3 has at least three positive edges and there can be no super negative cycle. 5. z = x 4 . First suppose v 4 x 4 ∈ C 1 , then σ (v 4 x 4 ) = -and by the assumption σ (v 1 x 1 ) = σ (v 1 y 1 ) = +. Therefore v 3 v 4 / ∈ C 1 , since otherwise there will be three positive edges in C 1 . However in this case v 3 v 4 is a chord of C 1 , this contradicts the Claim 8. Now suppose v 4 x 4 / ∈ C 1 , then z = v 4 and σ (v 4 x 4 ) = +. We now consider the super negative cycle C l containing v 4 x 4 (= zz ). As it must contain the positive edge v 2 v 3 as well, it can have no other positive edge. In particular, v 3 v 4 is not in C l . This implies that first of all v 4 y 4 ∈ C l and, secondly, that v 4 y 4 is a negative edge in (G, σ ). But then, by the assumption of σ (v 1 x 1 ) = σ (v 1 y 1 ) = +, the cycle C l contains three positive edges, contradiction with C l being a super negative cycle because it must contain at least one of v 1 x 1 , v 1 y 1 and v 2 x 2 , all of whom are positive.

6. z = x 1 . If v 1 x 1 = v 1 z is in C 1 , then it must be a negative edge of C 1 . Thus v 1 is
incident to at most one positive edge. The assumption of the claim implies that all edges incident to v 4 are positive. That implies v 4 / ∈ C 1 as otherwise C 1 will have at least three positive edges. As each positive edge of C 1 should be incident to one of v 1 , v 2 , v 3 , the second positive edge of C 1 can only be either v 1 y 1 or v 2 x 2 , in either case it follows that v 1 v 2 is a chord of C 1 , a contradiction with Claim 8.

So we may assume v 1 x 1 / ∈ C 1 . This implies that z = v 1 and that σ (v 1 x 1 ) = +. As C 1 has no chord, v 1 / ∈ C 1 . This implies v 2 x 2 ∈ C 1 and since σ (v 2 x 2 ) = +, it is the only other positive edge of C 1 . Thus v 3 v 4 / ∈ C 1 and hence, v 3 x 3 ∈ C 1 . We now claim that x 1 x 2 ∈ C 1 , that is because otherwise in the union of C 1 and the path x 1 v 1 v 2 we will find a shorter super negative cycle. Moreover, we observe that σ (x 1 x 2 ) = -. We now consider the cycle C 1 obtained from C 1 by replacing x 1 x 2 v 2 with x 1 v 1 v 2 . This cycle is also a super negative cycle of (G, σ ) and is of the same length as C 1 . Thus there must be a vertex z 1 of C 1 which is of degree three in G, and both edges of C 1 incident to z 1 are negative. Repeating the same argument as in cases 1-5, we conclude that z 1 ∈ {x 1 , y 1 }. The case z 1 = y 1 is not possible as otherwise C 1 contains a chord, and the case z 1 = x 1 is not possible because σ (v 1 x 1 ) = +.

Claim 13. Let v 1 , v 2 , v 3 , v 4 be vertices of degree 3 in G such that v i is adjacent to v i+1 , i = 1, 2, 3, where other neighbours of v i 's are labelled as in Figure 2. Then either each of x 2 and x 3 has at least three neighbours of degree at least 4, or one of x 2 and x 3 has at least four neighbours of degree at least 4.

Proof. Let G = G -v 2 v 3 and let σ 1 , σ 2 , σ 3 , σ 4 , σ 5 be the five signatures equivalent to σ such that, when restricted on G , they have no common negative edge. So v 2 v 3 can be the only common negative edge among some of these signatures. Each (G, σ i ) must contain a super negative cycle using the edge v 2 v 3 , one of which is named C i .

In each signature σ i , i = 1, . . . , 5, if v 2 x 2 and v 1 v 2 have the same sign, then by switching at v 2 and v 3 (if necessary), we can either be sure that all the super negative cycles have exactly two positive edges and that each of them is incident to either v 2 or v 3 . Then by Claim 11, there exists a super negative cycle C 1 such that every vertex not incident to a positive edge is of degree at least 4 in G. It is easy to observe that in at least three of the signatures σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , say σ 1 , σ 2 , and σ 3 , the edges v 2 x 2 and v 1 v 2 have the same sign. Since we only switch at v 2 and v 3 , in each of the signatures σ 1 , σ 2 , and σ 3 , either v 1 or x 2 has a negative neighbour of degree at least 4 in each of (G, σ 1 ), (G, σ 2 ), and (G, σ 3 ). If in each of (G, σ 4 ) and (G, σ 5 ) either the pair v 1 v 2 and v 2 x 2 have the same sign or the pair v 3 v 4 and v 3 x 3 have the same sign, then in total v 1 and x 2 , as well as v 4 and x 3 have five neighbours that are of degree at least 4 in G. As either v 1 or v 4 can have at most two such neighbours, x 2 and x 3 must have at least 3 of them. We note that the conclusion holds.

Hence we suppose σ 4 (v 1 v 2 ) = -σ 4 (v 2 x 2 ) and σ 4 (v 3 v 4 ) = -σ 4 (v 3 x 3 ). Since we can switch at either v 2 or v 3 (if necessary), we assume v 2 v 3 is positive. If σ 4 (v 2 x 2 ) = σ 4 (v 3 x 3 ), then we first make v 1 v 2 and v 3 v 4 to be negative by switching at v 2 and v 3 (if necessary). If at least one of v 1 x 1 and v 1 y 1 (resp. v 4 x 4 and v 4 y 4 ) is negative, then after switching at v 1 (resp. v 4 ), we will not create any new super negative cycle. Otherwise, both v 1 x 1 and v 1 y 1 (resp. v 4 x 4 and v 4 y 4 ) are positive. In either case, each cycle containing v 2 v 3 has at least three positive edges, which is a contradiction. Therefore, we may suppose σ 4 (v 2 x 2 ) = -σ 4 (v 3 x 3 ), and w.l.o.g. assume σ 4 (v 2 x 2 ) = +. By switching at v 1 , if necessary, we can make sure that v 1 is incident to at least two positive edges, let the obtained signature be σ 4 . Then the positive edges of each super negative cycle in (G, σ 4 ) must be incident to either v 1 or v 2 . Since σ 4 (v 3 v 4 ) = +, every super negative cycle of (G, σ 4 ) contains the edge v 3 x 3 . By Claim 12, there exists a super negative cycle such that every vertex not incident to a positive edge is of degree at least 4. Therefore, either x 3 has a negative neighbour (in (G, σ 4 )) of degree at least 4, or x 3 is adjacent to one of x 1 and y 1 . If we switch at v 2 and v 3 , by symmetry, we have that either x 2 has a negative neighbour (in (G, σ 4 )) of degree at least 4, or x 2 is adjacent to one of x 4 and y 4 . Now it suffices to consider two cases based on σ 5 .

Case 1:

Either σ 5 (v 1 v 2 ) = σ 5 (v 2 x 2 ) or σ 5 (v 3 v 4 ) = σ 5 (v 3 x 3 )
. Applying the same argument as conclude that for each (G, σ i ), i = 1, 2, 3, either v 1 or x 2 has a negative neighbour of degree at least 4. Similarly either v 4 or x 3 have a negative neighbour of degree at least 4. Since d(x 1 ) = d(x 4 ) = 3, both x 2 and x 3 have at least two neighbours of degree at least 4. Suppose the conclusion of the claim does not hold, assume x 2 has at most two neighbours of degree at least 4, w.l.o.g. assume x 2 is adjacent to x 4 . Since x 3 can have at most three neighbours of degree at least 4, x 3 is adjacent to either x 1 or y 1 , which implies x 2 has at least three neighbours of degree at least 4, a contradiction.

Case 2: σ 5 (v 1 v 2 ) = -σ 5 (v 2 x 2 ) and σ 5 (v 3 v 4 ) = -σ 5 (v 3 x 3 ). Applying the same argument as for σ 4 , either x 2 has a negative neighbour (in (G, σ 5 )) of degree at least 4, or x 2 is adjacent to one of x 4 and y 4 . Similarly either x 3 has a negative neighbour (in (G, σ 5 )) of degree at least 4, or x 3 is adjacent to one of x 1 and y 1 . Again we suppose the conclusion does not hold, and assume x 2 has at most two neighbours of degree at least 4. W.l.o.g. let x 2 be adjacent to x 4 and σ 4 (x 2 x 4 ) = -. Since x 3 can have at most three neighbours of degree at least 4, w.l.o.g. we assume x 3 is adjacent to x 1 and σ 4 (x 1 x 3 ) = -. Therefore, both x 2 and x 3 have at least two neighbours of degree at least 4. Hence, it must be the case that x 2 is adjacent to y 4 and σ 5 (x 2 y 4 ) = -, which implies that x 3 has three neighbours of degree at least 4. But then x 3 must be adjacent to y 1 and σ 5 (x 3 y 1 ) = -, which implies x 2 has three neighbours of degree at least 4, a contradiction.

Discharging

In the following, we will use the discharging technique to get a contradiction. The initial charge ω on V (G) ∪ F (G) is defined as follows: ω(x) = d(x) -4 for every x ∈ V (G) ∪ F (G). For brevity, we call a 4 + -vertex big, and a 3 --vertex small. For a vertex v, by n k (v) we denote the number of k-neighbours of v and by n b (v) the number of big neighbours of v. Given a face f , n k (f ) is the number of k-vertices incident to f . For x, y ∈ V (G) ∪ F (G), let τ (x → y) denote the charge transferring from x to y. For a 5-face

f = [v 1 v 2 • • • v 5 v 1 ],
if it is incident to exactly two small vertices, say d(v 1 ) = d(v 3 ) = 2, n b (v 2 ) = 3 and v 2 is not adjacent to any 3-vertex, then we call f and v 2 special. We will do discharging in three stages. Below are our needed discharging rules for first stage: After the first round of discharging, each 3-vertices which is adjacent to a 5 + -vertex v with n b (v) ≥ 4 or incident to a face f with n 3 -(f ) = 1, has a non-negative charge. If a 2-vertex is incident or adjacent to at least two of the following, then it would end up with a non-negative charge: face with only one small vertex or 5 + -vertex with four 3 + -neighbours. We call these small vertices rich. In the following rules, if not specified, the small vertices that we consider are those who remain negative, and refer to them as poor vertices. We use 5 i -face to denote 5-face incident to i poor vertices. A 3-vertex is called 3 k,l -vertex, if it is adjacent to k vertices each of which has at least three big neighbours, at least two either rich or poor 3-neighbours, and is incident to l 5 2 -faces. 2 to the incident 2-vertex. First suppose f is incident to a 3 k,l -vertex. If k + l ≥ 2, then f sends 1 2 to the other 3-vertex; If k = 1 and l = 0, then f sends 1 6 to 3 1,0 -vertex and 1 3 to the other 3-vertex; If k = 0 and l = 1, and moreover it is incident to a 5 3 -face which contains no 2-vertex, then f sends 1 6 to this 3 0,1 -vertex, and 1 3 to the other 3-vertex. Otherwise, f sends 1 4 to each incident 3-vertex. (R4.4) If f is a 5 3 -face such that n 3 (f ) = 3 or a 5 4 + -face, then f does not give charge to any incident 3 k,l -vertex such that k + l ≥ 2, but sends 1 6 to each incident 3 1,0 -vertex, then distribute its remaining charge equally among the other incident 3-vertices.

Given a special face F with a special vertex v, a charge pot at (F, v) is the set of consecutively adjacent special faces whose special vertex is v, as shown in Figure 3. The total charge of the pot is the number of faces it contains as shown in (R5). After carrying out (R1)-(R4), we apply (R5) as follows.

Figure 3: Charge pot (R5) Special face contributes 1 to its charge pot, each 2-vertex in exactly one charge pot take needed charge such that its final charge is non-negative from its charge pot, and each 2-vertex in two different charge pots takes charge which together with the charge get from the special vertex is exactly one from each of its charge pot with respect to the special vertex.

First, we observe that the following facts are true. In what follows, we are going to show that ω * (x) ≥ 0 for all x ∈ V (G) ∪ F (G) and the charge pot is also non-negative.

Conjecture 5 .

 5 Every signed simple planar graph in G 11 ∪ G 10 packs.

Figure 2 :

 2 Figure 2: Four vertices of degree 3 in Claim 12

  By the relation v∈V (G) d(v) = f ∈F (G) d(f ) = 2|E(G)| and Euler's formula, the initial total charge of the vertices and faces satisfies the following:x∈V (G)∪F (G) ω(x) = x∈V (G)∪F (G) (d(x) -4) = -4|V (G)| + 4|E(G)| -4|F (G)| = -8.Since any discharging procedure preserves the total charge of G, after applying appropriate discharging rules to change the initial charge ω to the final charge ω * such that ω * (x) ≥ 0 for every x ∈ V (G) ∪ F (G), we can have the contradiction below:0 ≤ x∈V (G)∪F (G) ω * (x) = x∈V (G)∪F (G) ω(x) = -8,and thus completes the proof.

( R1 )

 R1 Let d(v) ≥ 5. If n b (v) ≥ 4, then v sends 1 to each adjacent small vertex. Otherwise if n 3 (v) + n b (v) ≥ 4, then v sends 1 to each 2-neighbour, and d(v)-4-n 2 (v) n 3 (v) to each 3-neighbour. (R2) Let d(f ) = 5. If n 3 -(f ) = 1,then f sends 1 to the incident small vertex.

( R3 )

 R3 For the 5 + -vertex v such that n b (v) ≤ 3 and n 3 (v) + n b (v) ≤ 3, each of them sends d(v)-4 n 2 (v) to each 2-neighbour. (R4) Suppose f is a non-special 5-face. Then (R4.1) If f is a 5 1 -face, f sends 1 to incident small vertex; (R4.2) If f is a 5 2 -face, then f sends 1 2 to each small vertex incident to f . (R4.3) If f is a 5 3 -face then (R4.3.1) If n 2 (f ) = 2 and n 3 (f ) = 1, then f sends 1 2 to each incident 2-vertex. (R4.3.2) If n 2 (f ) = 1 and n 3 (f ) = 2, then f sends 1

Fact 1 . 2 ≥ 6 .

 126 Let d(v) = 2 and N (v) = {v 1 , v 2 }, then n b (v 1 ) + n b (v 2 ) + n 3 (v 1 )+n 3 (v 2 )

Fact 2 .

 2 A non-special 5-face sends charge at least 1 2 to its incident 2-vertex.

Acknowledgement. We would like to thank Lan-Anh Pham for discussions. This work is supported by the ANR (France) project HOSIGRA (ANR-17-CE40-0022). The second author is supported by a Ph.D. scholarship from China Scholarship Council.

= 0 by (R1). Otherwise, by (R3), ω * (v) ≥ d(v) -4 -n 2 (v) × d(v)-4 n 2 (v) = 0. Since 4-vertex v does not participate in the discharging procedure, ω * (v) = ω(v) = d(v) -4 = 0.

Assume d(v) = 3. If v is rich, then it has non-negative charge. Suppose v is not rich. If v is incident to at least one 5 1 -face, then ω * (v) ≥ 3 -4 + 1 = 0 by (R4.1). Otherwise let N (v) = {v 1 , v 2 , v 3 }, denote by f i the face that is incident to v such that vv i and vv i+1 are its two boundary edges (indices modulo 3).

If v is adjacent to 2-vertex, say d(v 1 ) = 2, then by Claim 6, v 2 or v 3 has at least 4 big neighbours or in total they have at least 5 big neighbours. Since v is poor, w.l.o.g., assume n b (v 2 ) = 3 and n b (v 3 ) = 2. And the other neighbour of v 1 , say v 1 has at least 4 big neighbours. Since n 3 (v 2 ) + n b (v 2 ) ≥ 4, f 1 is incident to at most two poor vertices, thus

Let v 2 and v 3 be the other two vertices of f 2 . By Claim 5 and Claim 6, either both of them have degree at least 3 or one of them has degree 2 and the other has degree at least 4. Therefore, either τ

. Suppose now v is not adjacent to any 2-vertices. If v is also not adjacent to any 3-vertex, then by the fact that v is poor, Claim 5 and Claim 6, for i = 1, 2, 3, f i is either adjacent to three 3-vertices or it is a 5 2 -face, therefore τ (f i → v) ≥ 1 3 by (R4.2) and (R4.4). If v is adjacent to exactly one 3-vertex, say v 1 , then again f 2 is either incident to three 3vertices or f 2 is a 5 2 -face, therefore τ (f 2 → v) ≥ 1 3 by (R4.2) and (R4.4). Let f 1 = vv 1 x 1 y 1 v 2 and f 3 = vv 1 x 2 y 2 v 3 . Since f i , i = 1, 2, 3, cannot contain two 2-vertices, each of them sends at least 1 6 to v by (R4.3.2) and (R4.4). First if v is a 3 k,l -vertex, such that k + l ≥ 2, then ω * (v) ≥ -1 + 2 × 1 2 = 0 by (R1) and (R4.2). For cases that k + l ≤ 1, if k = 1, then we have ω * (v) ≥ -1 + 1 2 + 1 3 + 2 × 1 6 = 1 6 by (R1). If l = 1, we consider following cases. If v is incident to a 5 3 -face which contains no 2-vertex, then ω * (v) ≥ -1 + 1 2 + 1 3 + 1 6 = 0 by (R4.2) and (R4.3.2). Therefore we could always assume that τ (f 1 → v) ≥ 1 4 and τ (f 3 → v) ≥ 1 4 by (R4), which implies that ω * (v) ≥ -1 + 1 2 + 2 × 1 4 = 0 by (R4.2). Thus k = l = 0, we suppose f 1 , f 3 are 5 3 + -faces and f 2 is a 5 3 -face that contains no 2-vertex. By (R4), we still have that τ (f 1 → v) ≥ 1 4 and τ (f 3 → v) ≥ 1 4 . 1. First suppose both f 1 and f 3 do not contain any 2-vertex, if they are both 5 3 -faces, then both of them send a charge of 1 3 to v by (R4.4) and thus ω * (v) ≥ -1 + 3 × 1 3 = 0. So let f 1 be a 5 4 -face, then by Claim 13, n b (x 2 ) = 3. Then when d(y

3 by (R4.4), and when d(y

Then by Claim 4, n b (v 3 ) ≥ 2 and f 3 is a 5 2 -face, which contradicts with our assumption that f 3 is a 5 3 + -face. And we know that d(x 2 ) ≥ 3. By Claim 4 and the fact that f 1 is a 5

Otherwise f 3 is a 5 4 -face such that all the small vertices have degree 3, then by Claim 13, the third neighbour of x 2 has at least three big neighbours. The third face of v 1 is either a 5 2 -face or a 5 3 -face with no 2-vertex, therefore, either v 1 is a 3 1,1 -vertex or both v 1 and x 2 are 3 1,0 -vertices, by (R4.4), we always have

Suppose v is adjacent to two 3-vertices, say v 2 and v 3 . Let the other two vertices of f i be x i and y i in the clockwise order, i = 1, 2, 3. By Claim 10, n b (v 1 ) ≥ 2. Again, since f i , i = 1, 2, 3, cannot contain two 2-vertices, each of them sends at least 1 6 to v by (R4.3.2) and (R4.4).

2) and (R4.3.2). By (R4.3.2), f i sends charge at least 1 4 to v, except f 2 is a 5 5 -face. If one of x 2 and y 2 has degree 2, then by Claim 6, f 2 is a 5 2 -face. Then ω * (v) ≥ -1

2). If one of x 2 and y 2 has degree 3, say d(x 2 ) = 3, then by Claim 13, either one of v 1 or y 1 has at least four big neighbours, or both of them have at least three big neighbours. Therefore either f 1 is a 5 2 -face, or n b (v 1 ) ≥ 3 and

Therefore, we may assume both x 2 and y 2 have degree at least four, and τ (f 2 → v) ≥ 1 3 by (R4.4). If either y 1 or x 3 has degree at most 3, by symmetry say d(y 1 ) ≤ 3, then by Claim 6 and Claim 13, either f 2 is a 5 2 -face which implies ω * (v) ≥ -1 + 1 2 + 2 × 1 4 = 0 by (R4.2), or both v 1 and x 2 has at least three big neighbours. If n 3 (v 1 ) ≥ 2, then τ (v 1 → v) ≥ 1 2 by (R1) and thus ω * (v) > 0. So we suppose n 3 (v 1 ) = 1 and n b (v 1 ) = 3. Then d(x 1 ) ≥ 4 and τ (f

, we have ω * (v) ≥ 0. Therefore, we assume d(x 3 ) ≥ 4. If d(y 3 ) ≥ 4, then f 3 is a 5 2 -face which gives v enough charge. Otherwise d(y 3 ) = 2 since n 3 (v 1 ) = 1, then by Claim 4, either f 3 is again a 5 2 -face or f 3 is a 5 3 -face and v 3 is incident to a 5 2 -face and a 5 3 -face which contains no 2-vertex, in both cases τ (f 3 → v) ≥ 1 3 by (R4.2) and (R4.3.2). So we always have ω * (v) ≥ -1 + 3 × 1 3 = 0. In the following we may assume both y 1 and x 3 have degree at least 4. If both x 1 and y 3 have degree at least 3, then each f i sends at least 1 3 to v by (R4.2) or (R4.4), and

3 . Otherwise we may assume the face f = v 2 x 2 x 2 y 1 y 1 that v 2 incident is a 5 3 -face, both x 2 and y 1 must have degree at most 3. We first derive that d(y 1 ) = 3, since otherwise by Claim 5 and Claim 6, y 1 has at least four big neighbours. By Claim 4 and the fact that both x 1 and v are poor, n b (y 1 ) = 3 and thus τ (f 1 → v) ≥ 1 3 by (R4.3.2). By symmetry, either d(y 3 ) = 2 or d(y 3 ) ≥ 3, τ (f 3 → v) ≥ 1 3 . Thus we have ω * (v) ≥ -1 + 3 × 1 3 = 0. Finally suppose v is adjacent to three 3-vertices. Then by Claim 10, for i = 1, 2, 3, each f i is a 5 3 -face that contains no 2-vertex, thus sends at least 1 3 to v by (R4.4), and

rich, or it is incident or adjacent to at least two of the following, then it would end up with a non-negative charge by (R1) and (R4.1): 5 + -vertex which has at least four 3 + -neighbours, and face with only one 3 --vertex, and 5 1 -face.

Otherwise first suppose that v is adjacent to a 2-vertex v 1 . Then by Claim 5, v 2 has at least five big neighbours and both incident faces are 5 2 -faces and not special. So we have ω * (v) ≥ 2 -4 + 1 + 2 × 1 2 = 0 by (R1) and (R4.2). Suppose now v is adjacent to a 3-vertex v 1 . By Claim 6, v 2 has at least four big neighbours and both incident faces are 5 3 --faces and not special, thus by (R1), (R4.2) and (R4.

Then by the Fact 1, all the neighbours of v 1 and v 2 except v are big vertices. Thus the incident faces of v only contains one small vertex and v is rich.

Suppose d(v 1 ) ≥ 5 and d(v 2 ) = 4. If v 1 has at least four big neighbours, then by definition the incident faces of v are not special since otherwise v 2 is a special vertex, thus

If the incident faces of v are not special, then both of them contains only one small vertex which implies that v is rich. Otherwise by (R5) v would get enough charge such that ω * (v) ≥ 0.

Suppose both v 1 and v 2 have degree at least 5. If one of the incident faces of v is special, then, by (R5), ω * (v) ≥ 0. Otherwise, if at least one of v 1 and v 2 has at least four 3 +neighbours, then ω * (v) ≥ 2 -4 + 1 + 2 × 1 2 = 0 by (R1) and Fact 2. Suppose now both v 1 and v 2 have at most three 3 + -neighbours. Then by Fact 1, n b (v 1 ) = n b (v 2 ) = 3, thus for i = 1, 2 τ (v i → v) ≥ 1 2 by (R3). Since the incident faces are not special, each of them sends a charge of at least 1 2 to v. Therefore ω * (v) ≥ 2 -4 + 4 × 1 2 = 0. Let f ∈ F (G) and d(f ) = 5. If f is special, then by (R5) ω * (f ) ≥ 5 -4 -1 = 0. Thus we may assume f is not special. If f is incident to at most one small vertex, then by (R2)

Finally suppose f is a 5 4 + -face, it has non-negative charge by (R4.4).

It remains to show that every charge pot has non-negative charge. Observe that in a special face, every 4 + -vertex except the special vertex has at least 3 big neighbours by Fact 1. Let P be a charge pot with special vertex v which is obtained by k consecutive special faces

be the consecutive 2-vertices on the special faces. Then by (R5) ω(P ) = k and there are k + 1 2-vertices which will take charge from P . By (R3), v in total sends charge at least (k + 1) × k+1+3-4 k+1 = k to these 2-vertices. Let N (v 1 ) = {v, v 1 }, f 0 and f 1 be the incident faces of v 1 . If d(v 1 ) = 4, then f 0 contains only one small vertex and thus τ (f 0 → v) = 1 by (R2). Suppose v 1 ≥ 5, then τ (v 1 → v 1 ) ≥ 1 2 by (R3). If f 0 is not special with respect to v 1 , then τ (f 0 → v) ≥ 1 2 by (R4.2). Otherwise by (R5) v 1 gets charge 1 from v 1 and the charge pot respect to v 1 . By symmetry v k+1 gets charge at least 1 which 20 is not from v or the charge pot respect to v. Thus ω * (P ) ≥ k -(2(k + 1) -k -2) = 0. This completes our proof.

Concluding remarks

In this work, using the result of [START_REF] Naserasr | Packing signatures in signed graphs[END_REF] which itself is based on the 4-color theorem, we showed for every triangle free planar simple graph G, the signed graph (G, σ) has a packing number at least 5. Unlike the result of [START_REF] Naserasr | Packing signatures in signed graphs[END_REF], the discharging technique used here is based on a planar embedding of G and thus cannot be applied to the class of K 5 -minor-free graphs directly. However, an extension from planar graphs to K 5 -minor-free graphs is already shown in [START_REF] Naserasr | Homomorphisms of triangle-free graphs without a K 5 -minor[END_REF].

It is unclear if this result can be proved independent of 4-color theorem. It is also not clear how important is the choice of the all negative signature. More precisely we would like to ask: Question 8. What is the best possible lower bound on the packing number of planar signed graph of girth at least g?