Marie-Christine Costa
email: marie-christine.costa@ensta-paristech.fr

Dominique De Werra
email: dominique.dewerra@epfl.ch

M.-C Costa

C Picouleau

Minimal graphs for 2-factor extension

Keywords:

come

Introduction

Matching extension has been studied for a long time by many authors, see for instance [START_REF] Bai | Generalization of matching extensions in graphs (III)[END_REF], [START_REF] Plummer | Extending matchings in graphs: A survey[END_REF] and [START_REF] Wang | Bipartite matching extendable graphs[END_REF]. In [START_REF] Costa | Minimal graphs for matching extensions[END_REF] a different kind of matching extension has been explored: the goal was to characterize graphs G = (V, E) on n vertices with a minimum number of edges such that for every pair x, y of non adjacent vertices, there exists an (almost) perfect matching in G xy = (V, E ∪ xy). This work was motivated by a reliability problem in which edges subject to breakdowns could be reinforced so that to any pair xy of non adjacent vertices, one could associate reinforced edges to obtain an (almost) perfect matching M ∪ xy.

Here we intend to concentrate on the problem in which (almost) perfect matchings (1-factors) are replaced by 2-factors. The precise formulation will be given below. In [START_REF] Vandenbussche | Extensions to 2 -Factors in Bipartite Graphs[END_REF] a different 2-factor extension problem has been studied.

We will consider a simple finite graph G = (V, E) with n vertices and m edges. A pair u, v of vertices is a non-edge if uv / ∈ E. For any subset X ⊆ V the subgraph induced by X is denoted by G[X]. We write G -X = G[V \ X] and G -v for G -{v}. N (v) is the set of neighbors of a vertex v; δ(v) = |N (v)| is the degree of v; a p-vertex is a vertex of degree p; if δ(v) = n -1 then v is universal. The closed neighborhood of v is N [v] = N (v) ∪ {v}. δ(G) (resp. ∆(G)) is the minimum (resp. maximum) degree of the vertices in G. An induced path with p edges is called a p-path. By d(u, v) we denote the distance between u and v, i.e., the length of a shortest path (number of edges) between u and v in G.

A subset F ⊆ E is a 2-factor if every vertex v has exactly two edges in F which are incident in v. Equivalently F is a collection of vertex-disjoint cycles covering all vertices. C k (resp. K k ) is the cycle (resp. complete graph) on k vertices. K 4 with an edge missing is called a diamond.

For all definitions related to graphs, see [START_REF] Bondy | Graph Theory[END_REF].

We intend to determine, for any integer n ≥ 3, a graph G = (V, E) with n vertices and a minimum number of edges such that for every pair x, y of non adjacent vertices of G it is always possible to include the non-edge xy into a 2-factor, i.e., the graph G xy = (V, E ∪ {xy}) has a 2-factor F, F ⊃ xy. In such a case we shall say that xy has been extended (to a 2-factor). Definition 1.1 A graph G = (V, E) is 2-factor expandable (or shortly expandable) if every non-edge xy can be extended. Definition 1.2 An expandable graph G = (V, E) with |V | = n and with a minimum number of edges is a minimum expandable graph (meg(n)). The size |E| of its edge set is denoted by Exp 2 (n).

Our problem may be related to the idea of edge-criticality. This concept has been considered in various contexts (see for instance [2], [START_REF] Bondy | Graph Theory[END_REF], [START_REF] Grünewald | Independent sets and 2-factors in edge-chromaticcritical graphs[END_REF]). We may call a graph 2-factor edge-critical if it contains no 2-factor but for any non-edge uv there is a 2-factor in G uv (which necessarily uses uv). Our meg(n) are different : they may contain a 2-factor and they have a minimum number of edges. We state our main result which will be proved in the following sections: Proposition 1.1 The minimum size of a 2-factor expandable graph is:

• Exp 2 (3) = 2, Exp 2 (4) = 4, Exp 2 (5) = 6, Exp 2 (6) = 9, Exp 2 (7) = 10, Exp 2 (8) = 11, Exp 2 (9) = 12;

• Exp 2 (n) = 1 2 (3n -n 4 ) , n ≥ 10.
The paper is organized as follows. In Section 2 some elementary properties of expandable graphs will be stated for later use. Section 3 will be dedicated to the presentation of meg(n) for 3 ≤ n ≤ 9. In Section 4 a lowerbound for Exp 2 (n) will be established for n ≥ 10, while it will be shown in Section 5 that it is best possible. Variations of the construction for n = 8p will be presented in Section 5.3 to handle the case n = 0 mod [START_REF] Vandenbussche | Extensions to 2 -Factors in Bipartite Graphs[END_REF], n ≥ 14. Finally constructions will be given for 10 ≤ n ≤ 13 in Section 5.4. Some conclusions and suggestions for further research are presented in Section 6.

Properties of expandable graphs

We shall state some basic properties of minimal expandable graphs which will be used to compute Exp 2 (n).

Fact 2.1 If G = (V, E) is not expandable, any partial graph G = (V, E ), with E ⊂ E, is not expandable. Property 2.1 If G = (V, E) is expandable then G is connected.
Proof: If u and v are in two distinct components then clearly uv cannot be extended.

Property 2.2 If n ≥ 5 and δ(G) = 1 then Exp 2 (n) ≥ 3 2 n. Proof: Let u be a 1-vertex of G. If G is expandable then G -u induces a clique. Since n ≥ 5 we have m ≥ 3 2 n. Property 2.3 Let G = (V, E) be expandable, n ≥ 5. If v ∈ V is universal then m ≥ 3 2 (n -1). Proof: From Property 2.2 if there is a universal vertex then Σ u∈V δ(u) ≥ n - 1 + 2(n -1) = 3(n -1). Property 2.4 Let G = (V, E) be expandable. Let v be a 2-vertex of G with N (v) = {a, b} and ab ∈ E. If c ∈ N (a) ∩ N (b), c = v, then δ(c) ≥ 4.
Proof: Consider any extension of ab: the triangle (a, b, v) is in the 2-factor. Since c is necessarily covered by another cycle, we have δ(c) ≥ 4.

Property 2.5 Let G = (V, E) be expandable and u, v be two 2-vertices. If d(u, v) = 4 with a 4-path uu wv v from u to v then δ(w) > 3. 3 Meg(n) for 3 ≤ n ≤ 9

Proof: d(u, v) = 4 implies that u v ∈ E. Now if δ(w) ≤ 3 the non-edge u v cannot be extended. Property 2.6 Let n ≥ 7. If u, v are two 2-vertices and N (u) ∩ N (v) = ∅ then Exp 2 (n) ≥ 3 2 n. Proof: Let G be an expandable graph with m edges. If δ(G) = 1, from Property 2.2 we have m ≥ 3 2 n. Now let δ(G) ≥ 2. If w ∈ N (u) ∩ N (v)
We will compute Exp 2 (n) for small values of n.

• Exp 2 (3) = 2: Trivially P 3 the path on three vertices (Figure 1 left) is a meg(3).

Figure 1: P 3 , the paw, the butterfly.

• Exp 2 (4) = 4: The paw (see Figure 1 center) is expandable. If G = (V, E) is a meg(4) with |E| < 4 then from Property 2.1 G is a tree. So G is either P 4 or the claw. None of those is expandable.

• Exp 2 (5) = 6: The butterfly (see Figure 1 right) is expandable. Let G = (V, E) be a meg [START_REF] Grünewald | Independent sets and 2-factors in edge-chromaticcritical graphs[END_REF] with |E| ≤ 5. Then |E| < 3 2 n and from Property 2.2, δ(G) ≥ 2, so G is the cycle C 5 on five vertices which is not expandable. n 2 be the number of 2-vertices. We have 2

• Exp 2 (6) = 9: The graph G 6 (see Figure 2 left) is expandable. From Fact 2.1 it is sufficient to consider a meg(6), G = (V, E), with |E| = 8. If there is a 1-vertex v then G -v is K 5 and |E| = 11, a contradiction. So δ(G) ≥ 2. Let
≤ n 2 ≤ 4. Let n 2 = 2. We have δ(v i ) = 2, 1 ≤ i ≤ 2 and δ(v i ) = 3, 3 ≤ i ≤ 6. If v i ∈ N (v 1 ) ∩ N (v 2 ) then v i is universal which is impossible. Thus w.l.o.g. N (v 1 ) = {v 3 , v 4 }, N (v 2 ) = {v 5 , v 6 }. From Property 2.4 if v 3 v 4 ∈ E then δ(v 5 ) > 3, a contradiction. So w.l.o.g. v 3 v 4 , v 5 v 6 , v 3 v 5 , v 4 v 6 ∈ E. But v 3 v 6 ∈ E cannot be extended. Let n 2 = 3. W.l.o.g. δ(v 1 ) = δ(v 2 ) = δ(v 3 ) = 2, δ(v 4 ) = δ(v 5 ) = 3, δ(v 6 ) = 4. We have |N (v 6 ) ∩ {v 1 , v 2 , v 3 }| ≥ 2, so v 6 is universal a contradiction. Let n 2 = 4. W.l.o.g. δ(v 1 ) = δ(v 2 ) = δ(v 3 ) = δ(v 4 ) = 2. If δ(v 5 ) = δ(v 6 ) = 4 then |N (v 6 ) ∩ {v 1 , v 2 , v 3 , v 4 }| ≥ 2, so v 6 is universal a contradiction. So we have d(v 5 ) = 3, d(v 6 ) = 5 but |N (v 5 ) ∩ {v 1 , v 2 , v 3 , v 4 }| ≥ 2 and v 5 is universal a contradiction.
• Exp 2 (7) = 10: The graph G 7 (see Figure 2 right) is expandable. Let G = (V, E) be a meg [START_REF] Plummer | Extending matchings in graphs: A survey[END_REF] with |E| < 10. Then |E| < 3 2 n : from Property 2.2 we have δ(G) ≥ 2 and from Property 2.6 two 2-vertices have no common neighbor. Each 2-vertex has its proper neighbor of degree at least three, thus there are exactly three 2-vertices, says v 1 , v 2 , v 3 . Thus there are exactly four 3-vertices v 4 , v 5 , v 6 , v 7 and |E| = 9. Using Property 2.6 again, w.l.o.g.

v 1 v 2 , v 1 v 4 , v 2 v 5 , v 3 v 6 , v 3 v 7 ∈ E. If v 6 v 7 ∈ E then v 4 ∈ N (v 6 ) ∩ N (v 7
) and from Property 2.4 δ(v 4 ) > 3, a contradiction. So w.l.o.g. v 4 v 6 , v 5 v 7 , v 4 v 5 , v 6 v 7 ∈ E but v 4 v 7 cannot be extended.

• Exp 2 (8) = 11: One can check that G 8 (see Figure 3) is expandable. Let G = (V, E) be a meg [START_REF] Vandenbussche | Extensions to 2 -Factors in Bipartite Graphs[END_REF] with |E| < 11. From Properties 2.2 and 2.6 δ(G) ≥ 2 and each 2vertex has its proper neighbor of degree at least three. It follows that there are at most four 2-vertices. Since |E| ≤ 10 there are exactly four 2-vertices, says v 1 , v 2 , v 3 , v 4 , and four 3-vertices v 5 , v 6 , v 7 , v 8 . W.l.o.g.

v 1 v 2 , v 3 v 4 , v 1 v 5 , v 2 v 6 , v 3 v 7 , v 4 v 8 ∈ E. From Property 2.4 v 5 v 6 ∈ E. So v 5 v 7 , v 5 v 8 , v 6 v 7 , v 6 v 8 ∈ E, but v 5 v 6 cannot be extended.
• Exp 2 (9) = 12: One can check that G 9 (see Figure 4) is expandable. Let G = (V, E), |E| < 12, be a meg(9). Properties 2.2 and 2.6 imply that δ(G) ≥ 2 and each 2-vertex has its proper neighbor of degree at least three. Then there are at most four 2-vertices. It follows that Σ v∈V δ(v) ≥ 23 and |E| ≥ 12. So Exp 2 (9) = 12, a contradiction. So from now on we examine the case where δ(G) ≥ 2 and for any two 2-vertices u, v we have

N G (u) ∩ N G (v) = ∅. Let V 0 , V 1 , V 2 be a partition of V with V 0 = {v ∈ V : δ(v) = 2}, V 1 = {v ∈ V, δ(v) ≥ 3, ∃u ∈ V 0 , uv ∈ E}, V 2 = V -(V 0 ∪ V 1 ).
Each connected component of G[V 0 ] is isomorphic either to K 1 or to K 2 (in this second case its two vertices are denoted by v and v).

Every v ∈ V 1 is such that: |N (v) ∩ V 0 | = 1. If |V 0 | ≤ 1 then m ≥ 3n-1 2
. So from now on we have

|V 0 | ≥ 2 and V 1 = ∅. Let V 1 0 , V 2 0 be the partition of V 0 such that v ∈ V 1 0 if and only if N (v) ∩ V 0 = ∅, V 2 0 = V 0 \ V 1 0 . Define X 0 = {v ∈ V 1 0 : N (v) = {x, y}, xy ∈ E} and Y 0 = V 1 0 \ X 0 = {v ∈ V 1 0 : N (v) = {x, y}, xy ∈ E}. For v ∈ V 2 0 let N (v) = {v, x} with v ∈ V 2 0 , x ∈ V 1 , N (v) = {v, y} with v ∈ V 2 0 , y ∈ V 1 ; let Z 0 = {v, v |xy ∈ E} and W 0 = V 2 0 \ Z 0 .
For such v, v ∈ Z 0 , from Property 2.4 we have δ(x), δ(y) ≥ 4.

We will use a discharging procedure: a weight w(v) is assigned to every vertex v ∈ V . At each step of the process the w(v) are changed to w (v) in such a way that Σ v∈V w(v) = Σ v∈V w (v). At the beginning we take w(v) = δ(v) for every vertex v. When the procedure will be completed we will have Σ v∈V w (v) = 2m ≥ 3n -n 4 . The procedure consists of two steps. In the first one vertices r with δ(r) ≥ 4 and possibly some 3-vertices u with a 3-path usr such that s is a 2-vertex transfer part of their charge to all 2-vertices v with d(v, r) ≤ 2. In the second step 3-vertices u transfer part of their charge to all 2-vertices v with d(v, u) ≤ 2.

Moreover the weight of any vertex v ∈ V 0 will be modified exactly once; initially the vertex v is active; after increasing its charge, v will be considered as neutral for all further discharging operations.

We proceed as follows:

• As long as there is r with δ(r) ≥ 4 such that there exists an active v with d(v, r) = 1: we take w (v) = w(v) + 3 4 = 11 4 and w (r) = w(r) -3 4 ≥ 11 4 . Recall that no two vertices of V 0 share a same r.

From now on, each active vertex has all its neighbors of degree 2 or 3.

• For each r with δ(r) ≥ 4 such that there exists an active v with d(v, r) = 2: note that v / ∈ Z 0 otherwise δ(x) ≥ 4, a contradiction. We now consider the neighborhood of r.

δ(s) ≥ 3, ∀s ∈ N (r): From our assumption there are at most δ(r) vertices u i ∈ V 0 such that d(u i , r) = 2. Let u 1 , u 2 , . . . , u k with v = u 1 be the vertices which are active among those. Note that in the case where

u i ∈ V 1
0 there is either one 2-path or two disjoint 2-paths between r and u i . If there is one path from r to u i let x i be its internal vertex; if there are two paths, let x i , y i be their internal vertices. For u i ∈ V 2 0 there is exactly one 2-path from u i to r, let x i denotes its internal vertex. Let λ be the number of vertices x i and y i , i.e., the number of 2-paths between r and the vertices u i , i = 1, ..., k. We take w

(r) = w(r) -λ 4 , w (x i ) = w(x i ) -1 4 , w (y i ) = w(y i ) -1 4 , 1 ≤ i ≤ k.
In the case where u i ∈ V 1 0 and there is exactly one 2-path from u i to r we take w (y i ) = w(y i ) - 1 4 . Note that since λ ≤ δ(r) we have w (r) ≥ 3 and, from Property 2.6, x i and y i are discharged at most once so we have w (x i ) ≥ 11 4 and w (y i ) ≥ 11 4 . In the case where u i ∈ V 2 0 , let z i be a neighbor of x i distinct from r and u i , we take w

(z i ) = w(z i ) -1 4 ; note that z i / ∈ V 1 else, let s ∈ V 0 ∩ N (z i ), sz i x i u i ūi is a 4-path and from Property 2.5 δ(x i ) ≥ 4, a contradiction; if there is another active vertex u j ∈ V 2 0 with a 2-path u j x j z i , there is a 4-path between u i and u j so δ(z i ) ≥ 4; since z i / ∈ V 1 , z i transfers at most 1 4 δ(z i )
; hence, when the procedure ends, we have w

(z i ) ≥ 11 4 . Finally, we set w (u i ) = w(u i ) + 1 ≥ 11 4 if there are two 2-paths from u i to r, or w (u i ) = w(u i ) + 3 4 = 11 4 else, for 1 ≤ i ≤ k. -∃ s ∈ N (r) ∩ V 0 (s is neutral):
From our assumption we have (N (r) -{s}) ∩ V 0 = ∅. If v ∈ W 0 then there is a 4-path from v to s; by Property 2.5 the neighbor x of v has degree at least 4, a contradiction. Hence v ∈ V 1 0 . Consider the case where there are two 2-paths vxr, vyr: since s is a 2vertex, to extend vr any 2-factor must contain vr, rs and needs that at least one of x, y has a degree at least 4, a contradiction. Thus there is exactly one 2-path vxr. Let u 1 , . . . , u k with v = u 1 be the active vertices such that d(u i , r) = 2. As for u 1 , we have u

2 , . . . , u k ∈ V 1 0 with exactly one 2-path u i x i r; let y i = x i denote the second neighbor of u i , 1 ≤ i ≤ k. There are three cases to consider. * s ∈ V 1 0 : we have k ≤ δ(r)-1.
Let y s = r be the second neighbor of s. We suppose first that s has been charged by r in the first step of the procedure. Notice that either δ(y s ) = 3 and y s was not used before, or δ(y s ) ≥ 4 and its charge is at least δ(y s )-1 4 (δ(y s )-1) ≥ 3. We take

w (r) = w(r) -(k-1)
4 , w (y s ) = w(y s ) -1 4 . Second assume that s has been charged by y s , so the charge of r has not been modified: we take

w (r) = w(r) -k 4 . Then in both cases w (x i ) = w(x i ) -1 4 , w (y i ) = w(y i ) -1 4 , w (u i ) = w(u i ) + 3 4 , 1 ≤ i ≤ k.
Notice that x i and y i have not been discharged before because u i is the only 2-vertex in their neighborhood. Hence all vertices q involved here satisfy w (q) ≥ 11 4 . * s ∈ Z 0 : let N (s) = {s, x} (recall that xr ∈ E and δ(x) ≥ 4; so s is neutral). Since δ(x 1 ) = δ(y 1 ) = 3 we have x 1 , y 1 = x. From our assumption it does not exist

v ∈ V 0 ∩ N (x), v = s. So k ≤ δ(r) -2. We take w (r) = w(r) -k 4 , w (x i ) = w(x i ) -1 4 , w (y i ) = w(y i ) -1 4 , 1 ≤ i ≤ k, and w (u i ) = w(u i )+ 3 4 , 1 ≤ i ≤ k.
Hence all vertices q involved here satisfy w (q) ≥ 11 4 . * s ∈ W 0 : let N (s) = {s, x} (recall that y 1 r ∈ E). If u 1 ∈ X 0 then ry 1 cannot be extended, indeed rx 1 and rs must be in the 2-factor. So

u 1 ∈ Y 0 . Let N (x 1 ) = {u 1 , r, z}. Let z ∈ N (z), z = x 1 ; assume z ∈ V 0 . If rz ∈ E then srx 1
zz is a 4-path and from Property 2.5 δ(x 1 ) ≥ 4, a contradiction. Now we consider the case rz ∈ E:

First δ(r) = 4. Assume that u 1 , u 2 , u 3 with u 1 = v, u 2 = z , u 3 = s and d(r, u 3 ) = 2 are three active 2-vertices. Let rx 3 u 3 be the 2- path from r to u 3 . Since u 3 is active x 3 is a 3-vertex. At least one of x 3 y 1 , x 3 y 2 is a non-edge. W.l.o.g. y 1 x 3 ∈ E. This non edge cannot be extended: If a 2-factor F, y 1 x 3 ∈ F, exists then x 3 u 3 ∈ F , so rx 3 ∈ F , sr, x 1 u 1 , zz ∈ F . W.l.o.g rz ∈ F, rx 1 ∈ F , so x 1 z ∈ F ,
a contradiction. u 3 cannot be active. We do as follows:

w (r) = w(r) -1 2 = (4 -3 4 -1 2 ) = 11 4 , w (x 1 ) = w(x 1 ) -1 4 , w (y 1 ) = w(y 1 ) -1 4 , w (x 2 = z) = w(x 2 ) -1 4 , w (y 2 ) = w(y 2 ) -1 4 , and w (u 1 ) = w(u 1 ) + 3 4 , w (u 2 = z ) = w(u 2 ) + 3 4 . Second δ(r) ≥ 5.
Let k be the number of active 2-vertices distinct from s at distance 2 of r. We do as follows:

w (r) = w(r)-k 4 , w (x i ) = w(x i ) -1 4 , w (y i ) = w(y i ) -1 4 , w (u i ) = w(u i ) + 3 4 , 1 ≤ i ≤ k
. Now any neighbor of z has a degree at least 3. In the case δ(z) = 3 there does not exist a 2-vertex w, w = u 1 , d(z, w) = 2 else there is a 4-path between u 1 and w and z has degree greater than 3, a contradiction. So z has not been used before in the discharging procedure. We do as follows:

w (r) = w(r) -(k-1) 4 , w (z) = w(z) -1 4 , w (x i ) = w(x i ) -1 4 , w (y i ) = w(y i ) -1 4 , w (u i ) = w(u i ) + 3 4 , 1 ≤ i ≤ k. Since k ≤ δ(r) -1 all
vertices q involved here satisfy w (q) ≥ 11 4 . In the case δ(z) > 3, since all the neighbors of z have a degree at least 3, the case has been treated before and v is neutral: a contradiction.

From now on, any active

v ∈ V 0 is such that ∀r with δ(r) ≥ 4, d(v, r) ≥ 3. It follows that v ∈ Z 0 . • For each active v ∈ V 0 such that d(v, u) ≥ 4 for any u ∈ V 0 \ N [v] If d(v, u) = 4, there is a 4-path vxzx u, then from Property 2.5, δ(z) ≥ 4, a contradiction. So d(v, u) ≥ 5 for any u ∈ V 0 \ N [v].
We have two cases:

-v ∈ V 1 0 .
Remark that from the discharging procedure the charge of any 3-vertex at distance at most two of v has not been decreased before since

d(v, v ) > 3 for any 2-vertex v . Let N (v) = {x, y} and z ∈ N (x) ∪ N (y), z = v, x, y. We take w (v) = w(v) + 3 4 , w (x) = w(x) -1 4 , w (y) = w(y) -1
4 and w (z) = w(z) -1 4 . Hence w (v) = 11 4 and all vertices q involved here satisfy w (q) ≥ 11 4 .

-

v ∈ W 0 . Let N (x) = {v, z 1 , z 2 } and N (y) = {v, z 3 , z 4 }. If {z 1 , z 2 } ∩ {z 3 , z 4 } = ∅ we can suppose that z 1 = z 3 . Then xy cannot be extended since δ(z 1 ) = 3. Now {z 1 , z 2 } ∩ {z 3 , z 4 } = ∅. We take w (v) = w(v) + 3 4 , w (x) = w(x) -1 4 and w (z i ) = w(z i )-1 4 , 1 ≤ i ≤ 2.
In the case where v is active we also take

w (v) = w(v) + 3 4 , w (y) = w(y) -1 4 and w (z i ) = w(z i ) -1 4 , 3 ≤ i ≤ 4. Hence w (v) = 11 4 , w (v) ≥ 11
4 and all vertices q involved here satisfy w (q) ≥ 11 4 since for any 2-vertex s, s = v, v, we have d(s, z i ) ≥ 3, i = 1, . . . , 4.

Notice that until now, the only 3-vertices which have been discharged are at distance 1 or 2 of a 2-vertex.

• For each remaining active vertex v ∈ V 0 v is such that there is u ∈ V 0 with d(v, u) ≤ 3.
From Property 2.6, the case d(v, u) = 2 cannot occur. In the case where

d(v, u) = 1 we have v ∈ W 0 so u = v. There is no other verticex u in V 0 with d(v, u ) = 3, else either d(v, u ) = 2
, which is forbidden, or there is a 4-path vvxx u and δ(x) ≥ 4 from Property 2.5, a contradiction. So for any

u ∈ V 0 , u = v, v, d(v, u ) ≥ 4, d(v, u
) ≥ 4: this case has been handled before.

From now on each active

v ∈ V 0 is such that v ∈ V 1 0 and there is u ∈ V 0 with d(v, u) = 3. With the same arguments as for v, u ∈ V 1 0 . Let N (v) = {x, y}, N (u) = {x , y } and yx ∈ E (recall that δ(x) = δ(y) = δ(x ) = δ(y ) = 3).
We If there is z ∈ N (x) ∩ N (y), z = v, then δ(z) ≥ 4 otherwise xy cannot be extended: a contradiction since d(v, z) = 2. With a similar argument for u, we have:

Fact 4.1 N (x) ∩ N (y) = {v} and N (x ) ∩ N (y ) = {u}.
Let N (y) = {v, x , z} and N (x) = {v, x , y }. From Fact 4.1 xz, yx , yy / ∈ E and z = y , x , y . Assume there is a 2-vertex w with N (w) = {z, w }: if x z / ∈ E then there is a 4-path wzyx u and δ(y) ≥ 4, a contradiction; if x z ∈ E then, either one of the three edges xy , xw , w y is not in E and this edge cannot be extended, or G is not connected: indeed n ≥ 10, δ(x) = δ(w ) = δ(y ) = 3 and G the subgraph induced by the nine vertices u, v, w, x, y, z, w , x , y is isomorphic to G 9 (see Figure 4) and not connected to the rest of G, a contradiction. Thus there is no 2-vertex at distance 1 of z.

If there is a 2-vertex w , w = v, u, with d(w , z) = 2 then there is a 4-path w wzyv and δ(z) ≥ 4, a contradiction. Thus there is no 2-vertex w, w = u, v, with d(w, z) ≤ 2, so z has not been discharged before.

Remember that any 3-vertex with an active vertex in the neighborhood has not been discharged. Thus w(x) = w(y) = w(z) = 3. We take w (v) = w(v) + 3 4 , w (x) = w(x) - 1 4 , w (y) = w(y) -1 4 and w (z) = w(z) -1 4 . This discharging is made for all the active vertices.

For each active vertex v we have considered its neighborhood {x, y} plus a vertex z at distance 2 of v which has no other 2-vertex at distance 1 or 2. Thus the weight of each vertex x, y, z associated to an active vertex v is decreased exactly once. Hence all vertices q involved here satisfy w (q) ≥ 11 4 .

The discharging procedure is done for all active vertices and ∀v ∈ V, w (v)

≥ 11 4 . So 2m = Σ n i=1 w(v) = Σ n i=1 w (v) ≥ 11 4 n. Thus m ≥ 1 2 (3n -n 4 ) .
5 Meg(n) for n ≥ 10

A basic module

To build the minimum expandable graphs we define their components. Figure 5 gives the component H. The graph H(2) is as follows (see Figure 6):

H(2) contains 2 copies H 1 , H 2 of H. The vertices of H i are denoted by a i , b i , . . . , h i , 1 ≤ i ≤ 2. The edges between H 1 and H 2 are are a 1 b 2 , b 1 a 2 , c 1 c 2 , d 1 d 2 .
Notice that since H 2 is a copy of H 1 , there are symmetries in H(2). In each module, a i , c i , e i , g i is symmetric to b i , d i , f i , h i and a i (resp. b i ) and c i (resp. d i ) play identical roles. As a consequence, if there is a 2-factor containing, for instance, the non-edge a 1 f 1 then, by symmetry, there is also a 2-factor containing c 1 f 1 as well as a 2-factor containing b 1 e 1 or d 1 e 1 , a 2 f 2 , b 2 e 2 , d 2 e 2 , c 2 f 2 . Also, a 1 c 2 plays the same role as a 1 d 2 .

The graph H(p), p ≥ 3, is built from H(p -1) as follows (see Fig. 7): add one copy H p of H to H(p -1). The vertices of In the following, we shall shorten many proofs by referring to all these properties as symmetries.

H i = (V i , E i ) are denoted by a i , b i , . . . , h i , 1 ≤ i ≤ p.
Remark 5.1 The graph H p has a 2-factor: for instance, take the cycle (a 1 , b 2 , a 2 , ..., a p , b 1 , a 1 ) and the p cycles (c i , e i , g i , h i , f i , d i , c i ), i = 1, ..., p.

Remark 5.2 The subgraph induced by

V i ∪V i+1 , 1 < i < p, is hamiltonian. A hamil- tonian cycle is (a i , b i , f i , h i , g i , e i , c i , d i , c i+1 , d i+1 , f i+1 , h i+1 , g i+1 , e i+1 , a i+1 , b i+1 , a i ).

Meg(n) for

n = 8p, p ≥ 2
We use a recurrence to prove that H(p) is a meg(8p).

Property 5.1 H(2) is a meg(16).
Proof: H(2) contains m = 22 = 1 2 (3 × 16 -16 4 ) edges. We show that H(2) is expandable. Let xy ∈ E. We give, first a chain (x, . . . , y), and then, possibly, a set of cycles that provide a 2-factor of H(2).

• xy = a 1 c 1 : (a 1 , e 1 , g 1 , h 1 , f 1 , b 1 , a 2 , b 2 , f 2 , h 2 , g 2 , e 2 , c 2 , d 2 , d 1 , c 1 ); by symmetry b 1 d 1 , b 2 d 2 , a 2 c 2 can be extended; • xy = a 1 d 1 : (d 1 , c 1 , e 1 , g 1 , h 1 , f 1 , b 1 , a 2 ,
• xy = a 1 f 1 : (f 1 , h 1 , g 1 , e 1 , c 1 , d 1 , d 2 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 2 , b 1 , a 1 ); by symmetry d 1 e 1 , c 1 f 1 , b 1 e 1 , c 2 f 2 , d 2 e 2 , a 2 f 2 , b 2 e 2 can be extended; • xy = a 1 g 1 : (g 1 , h 1 , f 1 , b 1 , a 2 , b 2 , f 2 , h 2 ,
• xy = a 1 c 2 : (c 2 , d 2 , d 1 , c 1 , e 1 , g 1 , h 1 , f 1 , b 1 , a 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 1 ); by symmetry b 1 d 2 , b 1 c 2 , a 1 d 2 , b 2 c 1 , d 1 b 2 , a 2 c 1 , a 2 d 1 can be extended. • xy = d 1 g 1 : (g 1 , h 1 , f 1 , b 1 , a 2 , b 2 , a 1 , e 1 , c 1 , c 2 , e 2 , g 2 , h 2 , f 2 , d 2 , d 1 ); by symmetry b 1 g 1 , c 1 h 1 , a 1 h 1 , c 2 h 2 , a 2 h 2 , d 2 g 2 , b 2 g 2 can be extended; • xy = e 1 a 2 : (e 1 , g 1 , h 1 , f 1 , b 1 , a 1 , b 2 , f 2 , h 2 , g 2 , e 2 , a 2 ), (c 1 , d 1 , d 2 , c 2 , c 1 ); by sym- metry b 2 f 1 , b 1 f 2 , a 1 e 2 , d 2 e 1 , c 2 f 1 , d 1 e 2 , c 1 f 2 can be extended; • xy = e 1 b 2 : (e 1 , g 1 , h 1 , f 1 , d 1 , c 1 , c 2 , d 2 , f 2 , h 2 , g 2 , e 2 , a 2 , b 1 , a 1 , b 2 ); by symmetry a 2 f 1 , a 1 f 2 , b 1 e 2 , c 2 e 1 , d 2 f 1 , c 1 e 2 , d 1 f 2 can be extended; • xy = e 1 f 1 : (e 1 , g 1 , h 1 , f 1 ), (a 1 , b 1 , a 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 1 ), (c 1 , d 1 , d 2 , c 2 , c 1 )
; by symmetry e 2 f 2 can be extended;

• xy = e 1 d 2 : (e 1 , g 1 , h 1 , f 1 , d 1 , c 1 , c 2 , d 2 ), (a 1 , b 1 , a 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 1 ); by sym- metry a 2 e 1 , c 2 f 1 , b 2 f 1 , c 1 f 2 , d 1 e 2 , a 1 e 2 , b 1 f 2 can be extended; • xy = e 1 f 2 : (e 1 , g 1 , h 1 , f 1 , b 1 , a 1 , b 2 , a 2 , e 2 , g 2 , h 2 , f 2 ), (c 1 , d 1 , d 2 , c 2 , c 1
); by symmetry e 1 e 2 , f 1 f 2 , e 2 f 1 can be extended;

• xy = e 1 h 2 : (e 1 , g 1 , h 1 , f 1 , d 1 , c 1 , c 2 , d 2 , f 2 , b 2 , a 1 , b 1 , a 2 , e 2 , g 2 , h
2 ); by symmetry e 1 g 2 , f 1 h 2 , f 1 g 2 , e 2 g 1 , f 2 h 1 , f 2 g 1 , e 2 h 1 can be extended;

• xy = f 1 g 1 : (g 1 , h 1 , f 1 ), (b 1 , a 1 , e 1 , c 1 , d 1 , d 2 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 2 , b 1 )
; by symmetry e 1 h 1 , f 2 g 2 , e 2 h 2 can be extended;

• xy = g 1 b 2 : (g 1 , h 1 , f 1 , d 1 , d 2 , c 2 , c 1 , e 1 , a 1 , b 1 , a 2 , e 2 , g 2 , h 2 , f 2 , b 2 ); by symmetry c 2 g 1 , a 2 h 1 , d 2 h 1 , a 1 h 2 , d 1 h 2 , b 1 g 2 , c
1 g 2 can be extended;

• xy = g 1 d 2 : (g 1 , h 1 , f 1 , d 1 , d 2 ), (a 1 , e 1 , c 1 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 2 , b 1 , a 1 ); by sym- metry a 2 g 1 , c 2 h 1 , b 2 h 1 , c 1 h 2 , b 1 h 2 , d 1 g 2 ,
a 1 g 2 can be extended; Case 2. x, y / ∈ H 2 : by symmetry this is equivalent to Case 1. Case 3. x ∈ H 2 , y ∈ H 3 . For each xy, we give, first a chain (x, . . . , y), and then, possibly, a set of cycles that provide a 2-factor of H(3).

• xy = g 1 h 2 : (g 1 , h 1 , f 1 , d 1 , d 2 , f 2 , b 2 , a 2 , b 1 , a 1 , e 1 , c
• xy = a 2 a 3 : (a 2 , b 3 , f 3 , h 3 , g 3 , e 3 , a 3 ); (a 1 , b 1 , f 1 , h 1 , g 1 , e 1 , c 1 , d 1 , d 3 , c 3 , d 2 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 1 ); by symmetry b 2 b 3 , d 2 d 3 , c 2 c 3 can be extended; • xy = a 2 c 3 : (a 2 , b 3 , a 3 , e 3 , g 3 , h 3 , f 3 , d 3 , d 1 , c 1 , e 1 , g 1 , h 1 , f 1 , b 1 , a 1 , b 2 , f 2 , h 2 , g 2 , e 2 , c 2 , d 2 , c 3
); by symmetry d 2 b 3 can be extended;

• xy = a 2 d 3 : (a 2 , b 3 , f 3 , h 3 , g 3 , e 3 , a 3 , b 1 , a 1 , b 2 , f 2 , h 2 , g 2 , e 2 , c 2 , d 2 , c 3 , d 3 ), (c 1 , d 1 , f 1 , h 1 , g 1 , e 1 , c 1 ); by symmetry b 2 c 3 , c 2 b 3 , d 2 a 3 can be extended; • xy = a 2 e 3 : (a 2 , b 3 , a 3 , b 1 , a 1 , b 2 , f 2 , h 2 , g 2 , e 2 , c 2 , d 2 , c 3 , d 3 , f 3 , h 3 , g 3 , e 3 ), (c 1 , d 1 , f 1 , h 1 , g 1 , e 1 , c 1
); by symmetry f 2 b 3 , d 2 f 3 , e 2 c 3 can be extended;

• xy = a 2 f 3 : (a 2 , b 3 , a 3 , e 3 , g 3 , h 3 , f 3 ), (a 1 , b 1 , f 1 , h 1 , g 1 , e 1 , c 1 , d 1 , d 3 , c 3 , d 2 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 1 )
; by symmetry e 2 b 3 , f 2 c 3 , d 2 e 3 can be extended;

• xy = a 2 g 3 : (a 2 , b 3 , a 3 , e 3 , c 3 , d 2 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 1 , b 1 , f 1 , h 1 , g 1 , e 1 , c 1 , d 1 , d 3 , f 3 , h 3 , g 3 ); by symmetry h 2 b 3 , g 2 c 3 , d 2 h 3 can be extended; • xy = a 2 h 3 : (a 2 , b 3 , f 3 , d 3 , c 3 , d 2 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 1 , b 1 , a 3 , e 3 , g 3 , h 3 ), (c 1 , d 1 , f 1 , h 1 , g 1 , e 1 , c 1
); by symmetry g 2 b 3 , h 2 c 3 , d 2 g 3 can be extended;

• xy = b 2 a 3 : (b 2 , f 2 , h 2 , g 2 , e 2 , a 2 , b 3 , f 3 , h 3 , g 3 , e 3 , a 3 ), (c 1 , d 1 , d 3 , c 3 , d 2 , c 2 , c 1 ), (a 1 , b 1 , f 1 , h 1 , g 1 , e 1 , a 1
); by symmetry c 2 d 3 can be extended;

• xy = b 2 d 3 : (b 2 , a 2 , b 3 , a 3 , b 1 , a 1 , e 1 , g 1 , h 1 , f 1 , d 1 , c 1 , c 2 , e 2 , g 2 , h 2 , f 2 , d 2 , c 3 , e 3 , g 3 , h 3 , f 3 , d 3 )
; by symmetry c 2 a 3 can be extended;

• xy = b 2 e 3 : (b 2 , a 2 , b 3 , a 3 , b 1 , a 1 , e 1 , g 1 , h 1 , f 1 , d 1 , c 1 , c 2 , e 2 , g 2 , h 2 , f 2 , d 2 , c 3 , d 3 , f 3 , h 3 , g 3 , e
3 ); by symmetry f 2 a 3 , e 2 d 3 , c 2 f 3 can be extended;

• xy = b 2 f 3 : (b 2 , a 1 , e 1 , g 1 , h 1 , f 1 , b 1 , a 3 , b 3 , a 2 , e 2 , g 2 , h 2 , f 2 , d 2 , c 2 , c 1 , d 1 , d 3 , c 3
, e 3 , g 3 , h 3 , f 3 ); by symmetry e 2 a 3 , f 2 d 3 , c 2 e 3 can be extended;

• xy = b 2 g 3 : (b 2 , a 1 , e 1 , g 1 , h 1 , f 1 , b 1 , a 3 , e 3 , c 3 , d 3 , d 1 , c 1 , c 2 , d 2 , f 2 , h 2 , g 2 , e 2 , a 2 , b 3 , f 3 , h 3 , g 3 )
; by symmetry h 2 a 3 , g 2 d 3 , c 2 h 3 can be extended;

• xy = b 2 h 3 : (b 2 , a 2 , b 3 , f 3 , d 3 , c 3 , d 2 , f 2 , h 2 , g 2 , e 2 , c 2 , c 1 , d 1 , f 1 , h 1 , g 1 , e 1 , a 1 , b 1
, a 3 , e 3 , g 3 , h 3 ); by symmetry g 2 a 3 , h 2 d 3 , c 2 g 3 can be extended;

• xy = e 2 e 3 : (e 2 , g 2 , h 2 , f 2 , b 2 , a 2 , b 3 , a 3 , b 1 , a 1 , e 1 , g 1 , h 1 , f 1 , d 1 , c 1 , c 2 , d 2 , c 3 , d 3 , f 3 , h 3 , g 3 , e
3 ); by symmetry f 2 f 3 can be extended;

• xy = e 2 f 3 : (e 2 , g 2 , h 2 , f 2 , d 2 , c 2 , c 1 , d 1 , d 3 , c 3 , e 3 , g 3 , h 3 , f 3 ); (a 1 , e 1 , g 1 , h 1 , f 1 , b 1 , a 3 , b 3 , a 2 , b 2 , a 1 )
; by symmetry f 2 e 3 can be extended;

• xy = e 2 g 3 : (e 2 , g 2 , h 2 , f 2 , b 2 , a 2 , b 3 , a 3 , e 3 , c 3 , d 2 , c 2 , c 1 , d 1 , d 3 , f 3 , h 3 , g 3 ); (a 1 , b 1 , f 1 , h 1 , g 1 , e 1 , a 1
); by symmetry h 2 f 3 , f 2 h 3 , g 2 e 3 can be extended;

• xy = e 2 h 3 : (e 2 , g 2 , h 2 , f 2 , b 2 , a 2 , b 3 , f 3 , d 3 , c 3 , d 2 , c 2 , c 1 , d 1 , f 1 , h 1 , g 1 , e 1 , a 1 , b 1 , a 3
, e 3 , g 3 , h 3 ); by symmetry g 2 f 3 , f 2 g 3 , h 2 e 3 can be extended;

• xy = g 2 g 3 : (g 2 , h 2 , f 2 , b 2 , a 1 , b 1 , f 1 , h 1 , g 1 , e 1 , c 1 , d 1 , d 3 , f 3 , h 3 , g 3 ), (a 2 , e 2 , c 2 , d 2 , c 3 , e 3 , a 3 , b 3 , a 2 )
; by symmetry h 2 h 3 can be extended;

• xy = g 2 h 3 : (g 2 , h 2 , f 2 , b 2 , a 1 , b 1 , a 3 , e 3 , g 3 , h 3 ), (a 2 , e 2 , c 2 , d 2 , c 3 , d 3 , f 3 , b 3 , a 2 ), (c 1 , d 1 , f 1 , h 1 , g 1 , e 1 , c 1
); by symmetry h 2 g 3 can be extended; Proof:

H(p) contains m = 11p = 1 2 (3 × 8p -8p 4 ) edges.
The proof is by induction. From Properties 5.1 and 5.2, H(2) and H(3) are expandable. So for p ≥ 3 we assume that H(p) and H(p -1) are expandable.

We now prove that for any p ≥ 3, H(p + 1) is expandable.

Let xy ∈ H(p + 1). We examine several cases.

Case 1. x, y / ∈ V 1 ∪ V p+1 . Let F be a 2-factor containing xy in H(p). From Remark 5.3, a p b 1 ∈ F or d p d 1 ∈ F . If F contains a p b 1 but not d p d 1 then a p
2. x ∈ V 1 .
Case 2.1. y / ∈ V p ∪ V p+1 . From our assumption xy can be extended in H(p -1). If the 2-factor in H(p -1) contains a p-1 b 1 but not d p-1 d 1 then a p-1 b 1 is substituted for a p-1 b p a p b p+1 a p+1 b 1 ; adding the two cycles (c j , d j , f j , h j , g j , e j , c j ), p ≤ j ≤ p + 1, we have a 2-factor in H(p+1). By symmetry, the case where the 2-factor in H(p-1)

contains d p-1 d 1 but not a p-1 b 1 is equivalent. If both a p-1 b 1 and d p-1 d 1 are in the 2-factor of H(p -1), then a p-1 b 1 is substituted for a p-1 b p a p b p+1 a p+1 b 1 and d p-1 d 1 for d p-1 c p e p g p h p f p d p c p+1 e p+1 g p+1 h p+1 f p+1 d p+1 d 1 to obtain a 2-factor in H(p + 1). Fi- nally, if a p-1 b 1 , d p-1 d 1 /
∈ F , we add to F the hamiltonian cycle on V p+1 ∪ V p (see Remark 5.2) to obtain a 2-factor in H(p + 1). Case 2.2. y ∈ V p ∪ V p+1 . By symmetry, y ∈ V p+1 is equivalent to y ∈ V 2 and, if p ≥ 4, y ∈ V p is equivalent to y ∈ V 3 seen just before.

It remains the case p = 3, y ∈ V 3 : we remove from H(4) the modules H 2 and H 4 and we obtain H (2) isomorphic to H(2). Looking at the 2-factors obtained in H(2) for xy / ∈ E, x ∈ V 1 , y ∈ V 2 , we see that they all contain exactly three edges among

a 1 b 2 , b 1 a 2 , c 1 c 2 , d 1 d 2 . Thus in H (2), any 2-factor F containing xy / ∈ E, x ∈ V 1 , y ∈ V 3 contains
3. x ∈ V p+1 . Case 3.1. y ∈ V i , i = 2. If y ∈ V 1 , by symmetry, this equivalent to the case x ∈ V 1 , y ∈ V p+1 treated in Case 2.
If y ∈ V i , i = 3, ..., p -1, these cases are equivalent to cases x ∈ V 2 , y ∈ V p-i+3 which were treated in Case 1.

If y ∈ V p , this is equivalent to x ∈ V 2 , y ∈ V 3 treated in Case 1.

Case 3.2 y ∈ V 2 , p ≥ 4. There are two adjacent modules H i and H i+1 with i = 2 and i + 1 = p + 1. We remove these modules and add the edges a i-1 b i+2 and d i-1 c i+2 . We obtain a graph H (p -1) isomorphic to H(p -1) which has a 2-factor F containing xy by assumption. If a i-1 b i+2 ∈ F but d i-1 c i+2 / ∈ F then a i-1 b i+2 is substituted for a i-1 b i a i b i+1 a i+1 b i+2 ; adding the two cycles (c j , d j , f j , h j , g j , e j , c j ), i ≤ j ≤ i + 1, we have a 2-factor in H(p + 1). By symmetry, the case where

d i-1 c i+2 ∈ F and a i-1 b i+2 / ∈ F is equivalent. If both a i-1 b i+2 and d i-1 c i+2 are in the 2-factor of H (p-1), then a i-1 b i+2 is substituted for a i-1 b i a i b i+1 a i+1 b i+2 and d i-1 c i+2 for d i-1 c i , e i g i h i f i d i c i+1 e i+1 g i+1 h i+1 f i+1 d i+1 c
i+2 to obtain a 2-factor in H(p + 1). Finally, if neither a i-1 b i+2 nor d i-1 c i+2 are in the 2-factor of H (p -1), then adding the hamiltonian cycle covering V i ∪V i+1 (see Remark 5.2) we obtain a 2-factor in H(p+1).

Meg(n)

for n = 0 mod [START_REF] Vandenbussche | Extensions to 2 -Factors in Bipartite Graphs[END_REF], n ≥ 14 Now, we give minimal expandable graphs when n ≥ 10 is not a multiple of 8. The graphs H -1 (p), H -2 (p), p ≥ 2, are obtained from H(p) by contracting one edge g i h i , respectively two edges g i h i , g j h j , i = j. The vertex resulting of the contraction of gh is denoted by gh.

Property 5.4 H -1 (p) is a meg(8p -1), p ≥ 2 and H -2 (p) is a meg(8p -2), p ≥ 2.

Proof:

H -1 (p) contains m = 11p -1 = 1 2 (3 × (8p -1) -8p-1 4 ) edges. H -2 (p) contains m = 11p -2 = 1 2 (3 × (8p -2) -8p-2 4
) edges. From Properties 5.1 and 5.3 we have H(p) is a meg(8p), p ≥ 2. The 2-factor of H -1 (p), resp. H -2 (p), corresponds to the 2-factor of H(p) where the subsequence of two consecutive vertices g, h in H(p) is replaced by the contracted vertex gh in H -1 (p), resp. H -2 (p).

The graph H +1 (p), p ≥ 2, is obtained from H(p) by adding a 2-vertex i and the two edges ig, ih to H(p). Property 5.5 H +1 (p) is a meg(8p + 1), p ≥ 2.

For x = k, if y = a 1 we do as above by replacing the sequence ikj by kij. If y = a 1 , we do as follows: we know that g 1 a 1 can be extended in H(p); the corresponding 2-factor contains e 1 a 1 g 1 . Thus substituting e 1 a 1 g 1 for e 1 g 1 and adding (a 1 , i, j, k, a 1 ) we obtain a 2-factor of H +3 (p).

The graph H +4 (p), p ≥ 2, is obtained from H(p) by adding a diamond (i, j, k, l), ij ∈ E and the edge ia 1 to H(p). ) edges. Let xy ∈ E. If x, y ∈ {i, j, k, l} then to obtain a 2-factor of H +4 (p) we add the cycle (i, k, j, l, i) to the 2-factor of H(p) obtained for the extension of xy.

For xy = ij we do as follows: we take a 2-factor covering H(p) (see Remark 5.1) and the cycle (i, j, l, k, i) to obtain a 2-factor of H +4 (p).

Let x = i : we have y ∈ {i, j, k, l, a 1 }. First we suppose that y is not a neighbor of a 1 . We know that ya 1 can be extended in H(p), so in the corresponding 2-factor there is a cycle with the sequence ya 1 . Substituting ya 1 for yia 1 and adding the cycle (j, k, l, j) we have a 2-factor for H +4 (p). Now let y = e 1 : We know that e 1 f 1 can be extended in H(p). The corresponding 2-factor contains (e 1 , g 1 , h 1 , f 1 , e 1 ) and a cycle C with the edge a 1 b 1 . Substituting the sequence a 1 b 1 for a 1 ie 1 g 1 h 1 f 1 b 1 and adding (j, k, l, j) we have a 2-factor of H +4 (p). When y ∈ {b 1 , b 2 } we do as follows: e 1 f 1 can be extended in H(p), the corresponding 2-factor contains (e 1 , g 1 , h 1 , f 1 , e 1 ), a cycle C with a 1 y, and a cycle C with c 1 d 1 . So substituting the sequence a 1 y for a 1 iy, the sequence c 1 d 1 for c 1 e 1 g 1 h 1 f 1 d 1 and adding (j, k, l, j) we have a 2-factor of H +4 (p).

Let x = k (resp.x = j): We proceed as for x = i but instead of a 1 i we take a 1 iljk (resp. a 1 ilkj).

The graph H +5 (p), is obtained from H +2 (p) by subdividing the edge a 1 b 1 into the path a 1 lkb 1 , adding a 2-vertex r together with two edges rl, rk. See Figure 8. ) edges. From Property 5.6 we know that H +2 (p) is expandable. Let xy ∈ E. If xy is also an non-edge of H +2 (p) and the corresponding 2-factor contains a 1 b 1 then we substitute the sequence a 1 b 1 for a 1 lrkb 1 ; else if a 1 b 1 is not in the 2-factor, so we add the cycle (k, l, r, k) to the 2-factor. In both cases we obtain a 2-factor for H +5 (p). and(k, l, r, k) is a 2-factor.

Now let xy

= a 1 b 1 : (a 1 , b 2 , a 2 , b 3 , a 3 , . . . , b p , a p , b 1 ), (c 1 , j, i, e 1 , g 1 , h 1 , f 1 , d 1 , c 1 ), (c i , e i , g i , h i , f i , d i , c i ), 2 ≤ i ≤ p,
Let x = k (the case where x = l is symmetric). If y = a 1 : a 1 y can be extended in H +2 (p); the corresponding 2-factor contains the path a 1 • • • y; we substitute it for krla 1 • • • y and we have 2-factor for

H +5 (p). If y = a 1 : (k, r, l, a 1 ), (c 1 , d 1 , d p , c p , d p-1 , c p-1 , . . . , d 2 , c 2 , e 2 , g 2 , h 2 , f 2 , b 2 , a 2 , b 3 , f 3 , h 3 , g 3 , e 3 , a 3 , b 4 , f 4 , h 4 , g 4 , e 4 , a 4 , . . . , b p , f p , h p , g p , e p , a p , b 1 , f 1 , h 1 , g 1 , e 1 , i, j, c 1 ) is a 2-factor. Let x = r.
Remark that all 2-factors containing the non-edge ky contain also kr; to extend ry we replace kr by rk in these 2-factors.

Meg(n) for 10 ≤ n ≤ 13

The constructions given in the previous sections do not cover the cases 10 ≤ n ≤ 13. We give constructions for all the situations.

We start from the graph G 10 shown in Figure 9. Note that G 10 and G 10 -a are hamiltonian. Proof: G 10 contains m = 14 = 1 2 (3 × 10 -10 4 ) edges. Let xy ∈ E.

• xy = ad: (a, b, c, e, f, h, j, i, g, d) yields a 2-factor; by symmetry ae, jf, jg can be extended;

• xy = af : (a, b, c, e, g, d, f ), (h, i, j, h) yields a 2-factor; by symmetry ag, jd, je can be extended;

• xy = ah: (a, b, c, e, f, d, g, i, j, h) yields a 2-factor; by symmetry ai, jb, jc can be extended;

• xy = aj: (a, b, c, e, f, d, g, i, h, j) yields a 2-factor;

• xy = be: (b, a, c, e), (d, g, i, j, h, f, d) yields a 2-factor; by symmetry cd, hg, if can be extended;

• xy = bf : (b, a, c, e, g, d, f ), (h, i, j, h) yields a 2-factor; by symmetry cg, hd, ie can be extended;

• xy = bg: (b, a, c, e, f, d, g), (h, i, j, h) yields a 2-factor; by symmetry cf, he, id can be extended;

• xy = bh: (b, a, c, e, f, d, g, i, j, h) yields a 2-factor; by symmetry ci can be extended;

• xy = bi: (b, a, c, e, g, d, f, h, j, i) yields a 2-factor; by symmetry ch can be extended;

• xy = de: (d, f, h, j, i, g, e), (a, b, c, a) yields a 2-factor; by symmetry f g can be extended.

The graph G 11 shown in Figure 10 is obtained from G 10 by the addition of the vertex k, the removal of dg, ef and the addition of dk, ek, f k, gk to E. • xy = dg: (d, f, k, e, g), (a, b, c, a), (h, i, j, h) is a 2-factor; by symmetry ef can be extended;

• xy = ak: (a, b, c, e, g, i, j, h, f, d, k) is a 2-factor; by symmetry jk can be extended;

• xy = bk: (b, a, c, e, g, i, j, h, f, d, k) is a 2-factor; by symmetry ck, hk, ik can be extended.

The graph G 12 shown in Figure 11 is obtained from G 10 by the addition of the vertices k, l, the removal of dg, ef and the addition of dk, ek, f l, gl, kl to E. • xy = dg: (d, b, a, c, e, k, l, f, h, j, i, g) is a 2-factor; by symmetry ef can be extended;

• xy = kf : (k, l, g, e, c, a, b, d, f ), (h, i, j, h) is a 2-factor; by symmetry kg, dl, el can be extended;

• xy = ka: (k, d, f, l, g, e, c, b, a), (h, i, j, h) is a 2-factor; by symmetry lj can be extended;

• xy = kb: (k, d, f, l, g, e, c, a, b), (h, i, j, h) is a 2-factor; by symmetry kc, lh, li can be extended;

• xy = kj: (k, l, g, e, c, a, b, d, f, h, i, j) is a 2-factor; by symmetry la can be extended;

• xy = ki: (k, l, g, e, c, a, b, d, f, h, j, i) is a 2-factor; by symmetry kh, lb, lc can be extended. The graph G 13 shown in Figure 12 is obtained from G 10 by the addition of the vertices k, l, o, the removal of ac. {a, k, l, o} induce the diamond with ao ∈ E . Property 5.13 G 13 is a meg(13).

Proof: G 13 contains m = 18 = 1 2 (3 × 13 -13 4 ) edges. Let xy ∈ E. If x, y ∈ {a, k, l, o} then we take F the corresponding 2-factor of G 10 . F has bac as subsequence. Substituting bac for bc and adding (a, k, o, l, a) we have a 2-factor for G 13 . If xy = ao then (a, k, l, o) and an hamiltonian cycle of G 10 -a is a 2-factor for G 13 .

Let x = a. If y ∈ {d, f, h, j} we know from Property 5.10 that there exists a 2-factor F for G 10 which does not contain ac. So adding (k, l, o, k) we have a 2-factor for G 13 .

• y = c: (a, b, d, f, h, j, i, g, e, c), (k, l, o, k) is a 2-factor;

• y = e: (a, b, c, e), (d, g, i, j, h, f, d), (k, l, o, k) is a 2-factor;

• y = g: (a, b, c, e, f, d, g), (h, i, j, h), (k, l, o, k) is a 2-factor;

• y = i: (a, b, c, e, g, d, f, h, j, i), (k, l, o, k) is a 2-factor. Now when x ∈ {k, l, o} we use the 2-factors we obtained above for x = a: the first sequence begins with kola or loka or okla instead of a.

Conclusion

We have determined the values of Exp 2 (n) for all values of n. It could be interesting to characterize the meg(n), for instance by a (finite ?) collection of forbidden induced subgraphs. Furthermore one could consider a generalization of the basic problem: the edges of a complete graph K n are coloured in blue and in red. We want to color a minimal set of red edges in white so that any red edge uv can be extended to a 2-factor using only white edges. In our case, we had only white and red edges. Furthermore instead of just one red edge we could require that any appropriate

  then w is universal. If there are at most two 2-vertices we have Σ u∈V δ(u) ≥ (n -1) + 4 + 3(n -3) = 4n -6 and m ≥ 3 2 n for n ≥ 7. If a, b, c are three 2-vertices then any non-edge xy with x, y = a, b, c cannot be extended so δ(v) ≥ n -4 for all v = a, b, c. We have Σ u∈V δ(u) ≥ (n -1) + 6 + (n -4)(n -4) = n 2 -7n + 21 and m ≥ 3 2 n for n ≥ 7.

Figure 2 :

 2 Figure 2: G 6 and G 7 two minimal expandable graphs with 6 and 7 vertices.

Figure 3 :

 3 Figure 3: The graph G 8 is a meg(8).

Figure 4 :

 4 Figure 4: The graph G 9 is a meg(9).

Figure 5 :

 5 Figure 5: The subgraph H with two 2-vertices and six 3-vertices.

  Remove the two edges b 1 a p-1 and d 1 d p-1 of H ( p -1). Add the four edges b 1 a p , a p-1 b p , d 1 d p , c p d p-1 .The modules H i are arranged around a cycle and numbered clockwise from 1 to p. Notice that there is a symmetry on each side of H 1 between H i and H p-i+2 , for i = 2, ..., p/2 + 1. As for H(2), a i (resp. b i ) and

Figure 6 :

 6 Figure 6: Two representations of H(2). (The index vertices are omitted).

  c i (resp. d i ) play identical roles: this can be seen by looking at Figure7. If there is a 2-factor containing, for instance, a 1 f 2 then, there is also a 2-factor containing b 1 f 5 as well as a 2-factor containing c 1 f 2 or d 1 f 5 . Notice also that a p b 1 and d p d 1 , the two edges linking H p to H 1 play the same role.

Figure 7 :

 7 Figure 7: Two representation of H(5). (The vertex indices are omitted).

  d 2 and then we can build a 2-factor containing xy in H(3) from a 2-factor F containing xy in H(2). If b 1 a 2 ∈ F and d 1 d 2 / ∈ F , we substitute b 1 a 2 for b 1 a 3 b 3 a 2 and we add the cycle (c 3 , d 3 , f 3 , h 3 , g 3 , e 3 , c 3 ) to obtain a 2-factor in H(3). The case b 1 a 2 / ∈ F and d 1 d 2 ∈ F is symmetric. If b 1 a 2 ∈ F and d 1 d 2 ∈ F , we substitute b 1 a 2 for b 1 a 3 b 3 a 2 and d 1 d 2 for d 1 d 3 f 3 h 3 g 3 e 3 c 3 d 2 to obtain a 2-factor in H(3).

Remark 5 . 3

 53 Let xy / ∈ H(p), p ≥ 3. If x, y = h 1 then any 2-factor containing xy contains a p b 1 or d p d 1 . Proof: Let F be a 2-factor containing xy and assume that none of a p b 1 and d p d 1 are in F . To cover b 1 and d 1 , F must contain the edges b 1 a 1 , b 1 f 1 , d 1 c 1 and d 1 f 1 . Clearly these 4 edges cannot be completed in a 2-factor if x and y = h 1 . Property 5.3 H(p) is a meg(8p), p ≥ 4.

  b 1 is replaced by a p b p+1 a p+1 b 1 ; adding the cycle (c p+1 , d p+1 , f p+1 , h p+1 , g p+1 , e p+1 , c p+1 ) we have a 2-factor in H(p + 1). By symmetry, the case where d p d 1 ∈ H(p) and a p b 1 / ∈ H(p) is equivalent. If both a p b 1 and d p d 1 are in F , then a p b 1 is substituted for a p b p+1 a p+1 b 1 and d p d 1 for d p c p+1 e p+1 g p+1 h p+1 f p+1 d p+1 , d 1 to obtain a 2-factor in H(p + 1).

Case

  also exactly three edges among a 1 b 3 , b 1 a 3 , c 1 c 3 , d 1 d 3 or, equivalently, they all miss exactly one edge among a 1 b 3 , b 1 a 3 , c 1 c 3 , d 1 d 3 . To obtain a 2-factor in H(4), we make the following substitutions: if a 1 b 3 / ∈ F , we replace c 1 c 3 by c 1 c 2 d 2 c 3 and we add the cycle (c 2 , d 2 , f 2 , h 2 , g 2 , e 2 , c 2 ); if b 1 a 3 / ∈ F , we replace d 1 d 3 by d 1 d 4 c 4 d 3 and we add the cycle (c 4 , d 4 , f 4 , h 4 , g 4 , e 4 , c 4 ); if c 1 c 3 / ∈ F , we replace a 1 b 3 by a 1 b 2 a 2 b 3 and we add the cycle (c 2 , d 2 , f 2 , h 2 , g 2 , e 2 , c 2 ); if d 1 d 3 / ∈ F , we replace b 1 a 3 by b 1 a 4 b 4 a 3 and we add the cycle (c 4 , d 4 , f 4 , h 4 , g 4 , e 4 , c 4 ).

Case

Case 3 .

 3 3 y ∈ V 2 , p = 3. This is the last case: x ∈ V 4 and y ∈ V 2 . We remove the module H 3 from H(4) and add the edges a 2 b 4 and d 2 c 4 : we get a graph H (3) isomorphic to H(3) in which xy can be extended. Let F be the 2-factor of H (3) containing xy. Looking at the 2-factors given for H(3) to complete an edge xy / ∈ H(3) with x ∈ V 2 and y ∈ V 3 , we see that they all contain a 2 b 3 or d 2 c 3 . Equivalently, F contains a 2 b 4 or d 2 c 4 . If F contains a 2 b 4 but not d 2 c 4 then a 2 b 4 is substituted for a 2 b 3 a 3 b 4 ; adding the cycle (c 3 , d 3 , f 3 , h 3 , g 3 , e 3 , c 3 ) we have a 2-factor in H(4). By symmetry, the case where H (3) contains d 2 c 4 but not a 2 b 4 is equivalent. If both a 2 b 4 and d 2 c 4 are in F , then a 2 b 4 is substituted for a 2 b 3 a 3 b 4 and d 2 c 4 for d 2 c 3 e 3 g 3 h 3 f 3 d 3 c 4 to obtain a 2-factor in H (4).

Property 5 . 8 H

 58 +4 (p) is a meg(8p + 4), p ≥ 2.

  Proof:H +4 (p) contains m = 11p + 6 = 1 2 (3 × (8p + 4) -8p+44

Figure 8 :

 8 Figure 8: The graph H +5 (p) is a meg(11p + 7).

  Proof:H +5 (p) contains m = 11p + 7 = 1 2 (3 × (8p + 5) -8p+54

Figure 9 :

 9 Figure 9: The graph G 10 is a meg(10).

Figure 10 :

 10 Figure 10: The graph G 11 is a meg(11).

Figure 11 :

 11 Figure 11: The graph G 12 is a meg(12).

Figure 12 :

 12 Figure 12: The graph G 13 is a meg(13).

  4 A lower bound for Exp 2 (n), n ≥ 10We will concentrate in showing a lower bound of Exp 2 (n) for n ≥ 10. It will be shown in the next section that it is best possible.

	Lemma 4.1 If G = (V, E) is a meg(n), n ≥ 10, then m ≥ 1 2 (3n -n 4 ) .
	Proof: From Property 2.1 G is connected. If there is a 1-vertex then from
	Property 2.2, m ≥ 3 2 n. If two 2-vertices have a common neighbor then from Prop-erty 2.6, m ≥ 3 2 n.

  1 , c 2 , e 2 , g 2 , h 2 ); by symmetry g 1 g 2 , h 1 h 2 , h 1 g 2 can be extended;

	Property 5.2 H(3) is a meg(24).
	Proof: H(3) contains m = 33 = 1 2 (3 × 24 -24 4 ) edges.
	We show that H(3) is expandable. Let xy ∈ E.
	Case 1. x, y / ∈ H

3 . Looking at the 2-factors given for H(2), we observe that they all contain at least one of the two edges b 1 a 2 , d 1

Proof: H +1 (p) contains m = 11p + 2 = 1 2 (3 × (8p + 1) -8p+1 4

) edges. Observe that all 2-factors of H(p) contain gh. Let xy ∈ E. If x, y = i 1 then the 2-factor of H +1 (p) corresponds to the 2-factor of H(p) where g 1 h 1 in H(p) is replaced by g 1 i 1 h 1 in H +1 (p). If x = i 1 then gy / ∈ E or hy / ∈ E. W.l.o.g. assume that gy / ∈ E. Then the 2-factor of H +1 (p) corresponds to the 2-factor of H(p) where

The graph H +2 (p) is obtained from H(p) as follows: the two edges a 1 e 1 , c 1 e 1 are subdivided into the paths (a 1 , i, e 1 ), (c 1 , j, e 1 ), respectively; the edge ij is added.

Proof:

) edges. We show that H +2 (p) is expandable. Let xy ∈ E. In the case where x, y ∈ {a 1 , c 1 , e 1 } we proceed as follows: we know that xy can be extended in H(p); the corresponding 2-factor contains either the subsequence a 1 e 1 c 1 , or a 1 e 1 g 1 or c 1 e 1 g 1 . In the first case the subsequence is substituted for a 1 ie 1 jc 1 , in the second for a 1 ije 1 g 1 , in the third for c 1 jie 1 g 1 . So xy can be extended in H +2 (p). Now let x = i (the case where x = j is similar). If y = c 1 , g 1 , we know that e 1 y can be extended in H(p); the corresponding 2-factor contains e 1 g 1 ; we replace it by ije 1 g 1 . If y = c 1 (resp. y = g 1 ): in H(p), the 2-factor corresponding to the non-edge g 1 c 1 (resp. g 1 a 1 ) contains c 1 e 1 a 1 ; we replace it by c 1 je 1 ia 1 .

If y = g 1 : in H(p), the 2-factor corresponding to the non-edge g 1 a 1 contains c 1 e 1 a 1 ; we replace it by c 1 je 1 ia 1 .

So iy can be extended in H +2 (p). Now let x = e 1 . We know that g 1 y can be extended in H(p); the corresponding 2-factor contains both g 1 h 1 and a 1 e 1 c 1 (or c 1 e 1 a 1 , but from symmetry this case is the same). We substitute the first subsequence for e 1 g 1 h 1 and the second for a 1 ijc 1 and e 1 y can be extended in H +2 (p).

The graph H +3 (p), p ≥ 2, is obtained from H(p) by adding a triangle (i, j, k) and the two edges ia 1 , ja 1 to H(p).

) edges. Let xy ∈ E. If x, y ∈ {i, j, k} then the 2-factor of H +3 (p) corresponds to the 2-factor of H(p) plus (i, j, k).

Let x = i (the case x = j is the same): note that y ∈ {i, j, k, a 1 }. Suppose first that y is not a neighbor of a 1 in H(p): ya 1 can be extended to a 2-factor and substituting ya 1 for yikja 1 , (i = x), we have a 2-factor for H +3 (p). Now let y = e 1 . We know that e 1 f 1 can be extended in H(p). The corresponding 2-factor contains (e 1 g 1 h 1 f 1 e 1 ) and a cycle C with the edge a 1 b 1 . Substituting a 1 b 1 for a 1 jkie 1 g 1 h 1 f 1 b 1 we have a 2-factor of H +3 (p). Let y ∈ {b 1 , b 2 }; e 1 f 1 can be extended in H(p), and the corresponding 2-factor contains (e 1 , g 1 , h 1 , f 1 , e 1 ), a cycle C with the edges a 1 b 1 and a 1 b 2 , and a cycle C with the edge c 1 d 1 . So replacing a 1 y by a 1 jkiy and c 1 d 1 by c 1 e 1 g 1 h 1 f 1 d 1 we have a 2-factor of H +3 (p). subset of d red edges could be extended to a 2-factor by adding only white edges. More generally we could concentrate on k-factors, k ≥ 3, or even other structured set of edges.