Surface Embedding of Non-Bipartite k-Extendable Graphs

Abstract.For every surface,we find the minimum number k such that every non-bipartite graph that is embeddable in that surface is not k-extendable.In particular,we construct a family of 3-extendable graphs which we call bowtie graphs.This confirms the existence of an in finite number of 3-extendable non-bipartite graphs that are embeddable in the Klein bottle.

Key words:Non-bipartite graph,matching extension,surface embedding.

1 Introduction

A matchingMof a graphGis said to be extendable ifGhas a perfect matching containingM.A graph isk-extendable if it has a matching consisting ofkedges and every matching consisting ofkedges is extendable,where

Much attention to the theory of matching extension has been paid since it was introduced by Plummer[17]in 1980.We recommend Lov′asz and Plummer’s book[11]for an excellent survey of the matching theory,and[21,27]for recent progress.Interests in the matching extensions of graphs embedded on surfaces began with the charming result[19]that no planar graph is 3-extendable.We refer the reader to Gross and Tucker’s book[5]for basic notions on topological graph theory;see also[2].

Plummer[18]considered the problem of determining the minimum integerksuch that every Σ-embeddable graph is notk-extendable.Based on some partial results of Plummer,Dean[3]found the complete answer to this problem.

Theorem 1.1(Dean,Plummer).LetΣbe a surface of characteristic χ.Let μ(Σ)be the minimum integer k such that everyΣ-embeddable graph is not k-extendable.Then we have

Its proof made a heavy use of the Euler contribution technique,which dates back to Lebesgue[8],developed by Ore[14],and flourished by Ore and Plummer[15].

In a previous paper[12],we extended Theorem 1.1 by finding the minimum integerksuch that there is no Σ-embeddable(n,k)-graphs,where an(n,k)-graph is a graph whose subgraph obtained by removing anynvertices isk-extendable.This paper continues the study of this embeddable-extendable type of problems.We dig a little deeper by concentrating on non-bipartite graphs.Here is our main result.

Theorem 1.2.LetΣbe a surface of characteristic χ.Let μ′(Σ)to be the minimum integer k such that everyΣ-embeddable non-bipartite graph is not k-extendable.Then we have

Non-bipartite graphs differ from bipartite graphs in many aspects,even if we are concerned with only matching problems.For instance,Knig theorem states that the maximum size of a matching in a bipartite graph equals the minimum size of a vertex cover;see Rizzi[24]for a short proof.Taking a triangle as the graph under consideration,one may see immediately that non-bipartite graphs do not admit this beautiful property in general.

Another example is on the algorithmic complexity.Lakhal and Litzler[7]discovered a polynomial-time algorithm for the problem of finding the extendability of a bipartite graph.It is still unknown that whether the same extendability problem for non-bipartite graphs can be solved in polynomial time or not;see Plummer[20].

The sharp distinction between the appearances of Eqs.(1.1)and(1.2),also supports the above difference between bipartite and non-bipartite graphs in the theory of matching extensions.

A big part of the proof of Theorem 1.2 is to show the 3-extendability of some so-called bow-tie graphs.We think the family of bow-tie graphs is interesting also on its own right.We will confirm the infinity of the number of 3-extendable graphs which can be embedded onto the Klein bottle,and which are non-bipartite.An infinity number of such,but bipartite,graphs,were constructed recursively by Aldred,Kawarabayashi,and Plummer[1].

This paper is organized as follows.In the next section we list necessary notion and notation,as well as necessary known results in the field of surface embedding and matching extension of graphs.The stand-alone Section 3 is devoted to the extendability of the two families of Cartesian product graphs of paths and cycles,and of the bow-tie graphs denoted asC6??Pnfor oddn≥5.We also pose a conjecture for the 3-extendability of the general bow-tie graphs.In Section 4 we establish Theorem 1.2 with the aid of these extendability results.

2 Preliminaries

This section contains an overview of necessary notion and notation.LetG=(V,E)be a simple graph.We denote the number|V(G)|of vertices by|G|for short.Denote byδ(G)the minimum degree ofG,and byκ(G)the connectivity.

2.1 The surface embedding

A surface is a connected compact Hausdorffspace which is locally homeomorphic to an open disc in the plane.If a surface Σ is obtained from the sphere by adding some numbergof handles(resp.some numberof cross-caps),then Σ is said to be orientable of genusg(resp.non-orientable of non-orientable genus).We shall follow the usual convention of denoting the surface of genush(resp.non-orientable genusk)bySh(resp.Nk).

A 2-cell embedding of a graphGonto a surface is a drawing of the graphGon the surface such that the edges ofGcross only at the vertices ofG,and that every face is homeomorphic to an open disk.In this paper,we wording “embedding”always means 2-cell embedding.We say that a graphGis Σ-embeddable if there exists an embedding of the graphGon the surface Σ.The minimum valuegsuch thatGisSg-embeddable is said to be the genus ofG,denotedg(G).Any embedding ofGonSg(G)is said to be a minimal(orientable)embedding.Similarly,the minimum valuesuch thatGisN-embeddable is said to be the non-orientable genus ofG,denoted(G).For a general surface Σ,letg(Σ)be the genus of Σ.The Euler characteristicχ(Σ)is defined by

Any embedding ofGonN(G)is said to be a minimal(non-orientable)embedding.Working on minimal embeddings,one should notice the following two fundamental results,which are due to Youngs[26]and Parsons et al.[16]respectively.

Theorem 2.1(Youngs).Every minimal orientable embedding of a graph is2-cell.

Theorem 2.2(Parson,Pica,Pisanski and Ventre).Every graph has a minimal non-orientable embedding which is2-cell.

The formula of non-orientable genus of complete graphs was found by Franklin[4]in 1934 forK7,and by Ringel[22]in 1954 for the otherKn.Early contributors include Heawood,Tietze,Kagno,Bose,Coxeter,Dirac,and so on;see[22].The more difficult problem of finding the genus of complete graphs has been explored by Heffter,Ringel,Youngs,Gustin,Terry,Welch,Guy,Mayer,and so on.A short history can be found in the famous work[23]of Ringel and Youngs in 1968,who settled the last case.These formulas are as follows.

Theorem 2.3.Let n≥5.We have

2.2 The Euler contribution

LetG→Σ be an embedding of a graphGon the surface Σ.Euler’s formula states that

whereeis the number of edges ofG,andfis the number of faces in the embedding.Letxidenote the size of theith face containingv,i.e.,the length of its boundary walk.The Euler contribution ofvis defined to be

where the sum ranges over all faces containingv.One should keep in mind that a face may contribute more than one angle to a vertex.This can be seen from the embedding ofK5on the torus.From Euler’s formula,in any embedding of a connected graphG,we have

Thus there exists a vertexvsuch that

Such a vertex is said to be a control point of the embedding.This definition implies the following lemma immediately,see also[18,Lemma 2.5]or[3,Lemma 2.5]for its proof.

Lemma 2.1.Let G be a connected graph of at least3vertices.Let G→Σbe an embedding.Let v be a control point which is contained in x triangular faces.Then we have

2.3 The matching extension

LetGbe a graph andk≥0.Ak-matching ofGis a collection ofkpairwise disjoint edges.Perfect matchings are|G|/2-matchings.A near perfect matching of the graphGis a perfect matching of the graphG-vfor some vertexvofG.The most basic result for perfect matchings is Tutte’s theorem[25].

Theorem 2.4(Tutte).A graph G has a perfect matching if and only if for every vertex subset S,the subgraph G-S has at most|S|connected components with an odd number of vertices.

The graphGis said to bek-extendable if

·it has a perfect matching,and

·for anyk-matchingM,the graphGhas a perfect matching containingM.

The following basic property on the connectivity of extendable graphs can be found in[17].

Theorem 2.5(Plummer).Let k≥0and let G be a connected k-extendable graph.Then G is(k+1)-connected and δ(G)≥k+1.

Liu and Yu[9]found the following result for the extendability of Cartesian product graphs.

Theorem 2.6(Liu and Yu).Let G1be a k-extendable graph and G2be a connected graph.Then the Cartesian product G1×G2is(k+1)-extendable.

Plummer[19]also gave the famous result that no planar graph is 3-extendable.The next deeper result is due to Lou and Yu[10,Theorem 7];see also[27,Chapter 6].

Theorem 2.8(Lou and Yu).If G is a k-extendable graph of order at most4k,then either G is bipartite or the connectivity κ(G)of G is at least2k.

We also need the following result,whose proof can be found in[3,12].

Lemma 2.2.Let k≥1.Let G be a connected k-extendable graph embedded on a surfaceΣ.Let v be a vertex of G which is contained in x triangular faces in the embedding.Then we have

3 The matching extension of special product graphs

In this section,we shall establish the 3-extendability for some special graphs,which will be used in handling some sporadic cases in proving Theorem 1.2.

Denote byPmthe path havingmvertices.Denote byPm×Pn,as usual,the Cartesian product graph of the pathsPmandPn.We label its vertices byvi,j(or byvijif there is no confusion),from the northwest to the southeast,wherei∈[m]andj∈[n].We use the notationRito denote the vertex set{vi1,···,vin}of thei-th row;and use the notationTjto denote the vertex set{v1j,···,vmj}of thej-th column.We say that any edge in a row is horizontal,and that any edge in a column is vertical.For convenience,we consider the first subscriptiof the notationvijas modulom,and consider the second subscriptjas modulon,i.e.,

Figure 1:The bow-tie graph C6??P5is N2-embeddable.

It follows thatRi+m=Rifor alli,and thatTj+n=Tjfor allj.Denote byCnthe cycle havingnvertices.We use the same way to label the vertices of the graphsPm×CnandCm×Cn.

For any positive integersmandn,we define the bow-tie graphCm??Pnto be the graph obtained from the graphCm×Pnby adding the edgesvi1vm+2-i,nfor alli∈[m].From Fig.1,it is easy to see that the graphCm??PnisN2-embeddable.

In the subsequent three subsections,we will explore the matching extension of the following graphs respectively:

Precisely speaking,we will show that the graphPm×Cnis 2-extendable,and the other two graphs are 3-extendable,subject to some natural conditions on the integersmandn.

Here we describe a combinatorial idea,which will be adopted in all the proofs uniformly.LetGbe a graph with a matchingM.We say thatGis separable by a subgraphG′(with respect toM),if

· the matchingMhas at least one edge in the subgraphG′;and

·no edge of the matchingMhas ends in both of the subgraphsG′andG-V(G′).We call the subgraphG′anM-separator ofG,if

·the subgraphG′has a perfect matching containing the edge setM∩E(G′);and

·the subgraphG-V(G′)has a perfect matching containing the edge setM∩E(G-V(G′)).

In particular,the subgraphG-V(G′)has a perfect matching even if the setM∩E(G-V(G′))is empty.From the above definition,it is direct to see that the extendability of a matchingMcan be con firmed by finding anM-separator.We call this approach the separator method.We will use it uniformly by choosing the separator to be a subgraph induced by consecutive rows or columns.

3.1 The 2-extendability of the graph Pm×Cn

This subsection is devoted to establish the following result.It is basic and will be used in the proof of Lemma 3.1 and Theorems 1.2 and 3.2.

Theorem 3.1.Let m,n≥4.The Cartesian product graph Pm×Cnis2-extendable if and only if the integer m or n is even.

Proof.The necessity is clear from the definition.Whennis even,the cycleCnis 1-extendable.Thus the sufficiency is true from Theorem 2.6.It suffices to show the sufficiency for oddn.

Letn≥5 be an odd integer.Then the integermis even.LetGbe the graphPm×Cn,with a 2-matchingM={e1,e2}.Note that every column of the graphGis isomorphic to the pathPm,which has a perfect matching.We will adopt the separator method by finding some columns,whose induced subgraph has a perfect matching containing the matchingM.We have 3 cases to treat.

Case 1.There are two disjoint pairs of adjacent columns,such that one pair contains the vertex setV(e1),and the other pair contains the vertex setV(e2).Since the subgraph induced by any two adjacent columns is 1-extendable,the four columns form anM-separator.

Case 2.The vertex setV(M)is contained in two adjacent columns,and Case 1 does not occur.Then the two adjacent columns form anM-separator.In fact,when both the edgese1ande2are vertical and in distinct columns,the previous possibility happens,a contradiction.In other words,either the vertex setV(M)is contained in one column,or one of the edges in the matchingMis horizontal.

Case 3.Otherwise,the vertex setV(M)intersects with exactly three consecutive columns,and both the edgese1ande2are horizontal.

We proceed by induction onm.Form=4,we have 2 sub-cases to treat.

Case 3-1 Assume that the edges in the matchingMlie in Row 1 and Row 2,or in

Row 1 and Row 3.Since every row is isomorphic to a cycle,we can suppose

without loss of generality that

In this case,the subgraphG[T1,T2,T3,T4]has the perfect matching

which contains the matchingM,see Fig.2.

Figure 2:The extension of the matching M for Case 3-1.

Case 3-2 Otherwise,the edges in the matchingMlie in Row 1 and Row 4,or in

Row 2 and Row 3.We can suppose that

In this case,the subgraphG[T1,T2,T3]has the perfect matching

which contains the matchingM,see Fig.3.

Figure 3:The extension of the matching M for Case 3-2.

This completes the proof form=4.

Now we can suppose thatm≥6,and that the graphPm-2×Cnis 2-extendable.Note that the subgraph induced by any two adjacent rows has a perfect matching.By induction,we are done if the matchingMshares no vertices with the first two rows.For the same reason,we are done ifMshares no vertices with the last two rows.Sincem≥6,we can suppose that the horizontal edgee1is in the first two rows,and that the horizontal edgee2is in the last two rows.On one hand,the subgraphG[R1,R2]is isomorphic to the graphP2×Cn,which is 1-extendable.On the other hand,the subgraphG-R1-R2is isomorphic toPm-2×Cn,which is 2-extendable by induction hypothesis.Hence,the subgraphG[R1,R2]is anM-separator.This completes the proof.

3.2 The 3-extendability of the graph Cm×Cn

In this subsection we study the extendability of the graphCm×Cn,which will be used in the proof of Theorem 1.2.

A necessary condition for the graphCm×Cnto have a perfect matching is that one of the integersmandnis even.By symmetry,we can suppose that the integermis even.In virtue of Theorem 2.7,the graphCm×Cnis 3-extendable if the integernis also even.Therefore,we can suppose thatnis odd.The following lemma will be used for several times.

Lemma 3.1.Let m≥6be an even integer,and let n≥5be an odd integer.Let G be the graph Cm×Cn,with a3-matching M.Then the matching M is extendable if G is separable by

(i)a subgraph G[Ri,Ri+1]for some i∈[m],which contains exactly one edge of the matching M;or

(ii)a subgraph G[Tj,Tj+1]for some j∈[n],which contains one or two edges of the matching M.

Proof.We prove the validities of Condition(i)and Condition(ii)separately.Leti∈[m]andj∈[n].

(i)The graphG[Ri,Ri+1]is isomorphic toP2×Cn,which is 1-extendable.The subgraphG-Ri-Ri+1is isomorphic toPm-2×Cn.Sincem-2≥4,the graphGRi-Ri+1is 2-extendable by Theorem 3.1.Hence,the matchingMis extendable inG.

(ii)The graphG[Tj,Tj+1]is isomorphic toCm×P2,andG-Tj-Tj+1is isomorphic toCm×Pn-2.Both of them are 2-extendable by Theorem 2.7.Hence,the matchingMis extendable in the graphG.

Here is the main result of this subsection.

Theorem 3.2.Let m≥6be an even integer,and let n≥5be an odd integer.Then the Cartesian product graph Cm×Cnis3-extendable.

Proof.Letm≥6 be an even integer,and letn≥5 be an odd integer.LetG=Cm×Cn,with a 3-matchingM={e1,e2,e3}.In order to show thatMis extendable,it suffices to find

·a row indexi*such that the subgraphG[Ri*,Ri*+1]is anM-separator,or

·a column indexj*such that the subgraphG[Tj*,Tj*+1]is anM-separator.

Lethbe the number of horizontal edges in the matchingM.Then we haveh∈{0,1,2,3}.We treat these 4 cases individually.

Case 1.h=0,that is,all edges inMare vertical.Note that each column of the graphGis isomorphic to the cycleCm,which is 1-extendable.If the 3 edges inMare in distinct columns,we are done immediately.If they are in the same column,then that column together with one of its adjacent columns form anM-separator.Otherwise,we can suppose that Columnjcontains the edgese1ande2,but not the edgee3.By virtue of Lemma 3.1,we can takej*=jife3is not in Column(j+1);and takej*=j+1 otherwise.

Case 2.h=1.In this case,we can suppose thate1is horizontal,and thate2ande3are vertical.Since each row is isomorphic to a cycle,we can further suppose thate1=vi1vi2and it intersects with the first two columns.

If at most one of the edgese2ande3is in the first two columns,then we can takej*=1 by Lemma 3.1.Otherwise,both of them are in the first two columns.If the vertex setV(M)misses Row(i+1),then we can takei*=iby Lemma 3.1.For the same reason,we can takei*=i-1 ifV(M)misses Row(i-1).Otherwise,one of the edgese2ande3is immediately above the horizontal edgee1,and the other is immediately belowe1.In this case,we can takei*=i+1 by Lemma 3.1.

Case 3.h=2.We can suppose thate1ande2are horizontal,and thate3is vertical.Furthermore,we can suppose that the horizontal edgee1intersects with the first two columns,the horizontal edgee2intersects with Columnjand Column(j+1),and that the vertical edgee3=vpqvp+1,q,wherep∈[m]andq∈[n].

Ifj=1,to wit,the horizontal edgee2lies below the edgee1.In this case,we can takej*=1.In fact,sincee3is vertical,the graphGis separable by the subgraphG[T1,T2].On the other hand,it is easy to see that both of the subgraphs are 1-extendable.

Ifj≥3,then the graphGis separable by the first two columns with respect to the matchingM.In this case,we can also takej*=1,by using Lemma 3.1.

Otherwise,we havej=2,that is,the vertex set of the horizontal edgese1ande2intersects with exactly the first three columns.

·Ifq∈[3],i.e.,the edgee3is also contained in the subgraphG[T1,T2,T3],then we can takei*=p.In fact,the subgraphG′=G[Rp,Rp+1]contains the vertical edgee3,and possibly one of the edgese1ande2.In any case,the matchingM∩E(G′)is extendable in the subgraphG′.

·Ifq≥4,i.e.,the vertical edgee3has empty intersection with the first three columns.In this case,the subgraphG[Tq]is anM-separator.In fact,the subgraphG[Tq],which contains the edgee3,is isomorphic to the cycleCm,which is 1-extendable.On the other hand,the subgraphG-Tqis isomorphic to the graphCm×Pn-1,i.e.,the graphPn-1×Cm.Sincen-1≥4,it is 2-extendable by Theorem 3.1.

Case 4.h=3.If all edges inMlie in the same row,by Lemma 3.1,we can takej*=jfor any edgevijvi,j+1∈M.Otherwise,there exists a rowRicontaining exactly one edge inMsuch that one of its adjacent rows has no edges inM.In other words,either

By Lemma 3.1,we can takei*=i-1 in the former case,andi*=iin the latter case.This completes the proof.

We remark that the graphC4×Cnis not 3-extendable whennis odd.This can be seen from the fact that the particular 3-matching

is not extendable,see Fig.4.define

We have|U|=2n-4.Note that the subgraphG-V(M)-Uconsists of 2n-2 isolated vertices.By Theorem 2.4,the subgraphG-V(M)has no perfect matchings.

Figure 4:The graph C4×Cnis not 3-extendable when n is odd.

3.3 The 3-extendability of the graph C6??Pnfor odd n≥5

In this subsection,we will show the 3-extendability of the graphC6??Pnfor odd integersn≥5.It is easy to see thatC6??Pncan be drawn as in Fig.5,which is symmetric up and down.For convenience,we rename the vertices in the following way:

and use capital letters to denote vertex subsets as follows:

Let us keep in mind that the subscriptiin the symbolshiare considered modulon,and the subscriptiin the symbolsqiare modulo 2n,namely,

Theorem 3.3.Let n≥5be an odd integer.Then the bow-tie graph C6??Pnis3-extendable.

Proof.LetG=C6??Pn,wherenis an odd integer andn≥5.

LetM0be a 3-matching of the graphG.We call an edge ofM0faithful if it is an edge of the subgraphG[J];co-faithful if it is an edge of the subgraphG[J′];and unfaithful otherwise,i.e.,if it is an edge of the formqjq′jfor somej∈[2n].Correspondingly,we call a vertex of the matchingM0faithful(resp.co-faithful,unfaithful)if it is a vertex of a faithful(resp.co-faithful,unfaithful)edge.

Figure 5:The graph C6??Pn.

Suppose that the matchingM0hasxfaithful edges,yunfaithful edges,andzco-faithful edges.Then we havex+y+z=3.By the symmetry of the graphG,we can suppose thatx≥z.Then we havez=0 orz=1.For each of them,we will construct a perfect matching of the graphGwhich extends the matchingM0.

The following lemma serves for Lemma 3.3,by which we can solve the casez=0.The other casez=1 can be divided into the cases

We will handle them by Lemmas 3.4 and 3.5 respectively.

Lemma 3.2.Every3-matching of the subgraph G[J]can be extended to a matching covering the vertex set H.

Proof.Suppose that the claim is false.LetM0be a 3-matching which is not extendable in this way.LetfMbe an extension ofM0,which covers the maximum number of vertices in the setH.Without loss of generality,we can suppose thath1/∈V(fM).Thenq1,qn+1∈V(M0),and we can write

wheree2∈{qnqn+1,qn+1qn+2}.We will find a contradiction by constructing an extension ofM0,which coversH.It suffices to find a matchingMof the subgraphG[H]-V(M0)such that the subgraphG[H]-V(e3)-V(M)consists of paths of even orders.We proceed according to the number of vertices inHcovered by the edgee3.

Case 1.IfV(e3)∩H=?,then we can define

Case 2.If|V(e3)∩H|=1,then we can defineM=?.

Case 3.If|V(e3)∩H|=2,then we havee3=hihi+1,wherei∈{2,···,n-1}.We can define

This proves Lemma 3.2.Here is the lemma by using which the casez=0 can be solved.

Lemma 3.3.Suppose that the matching M0has no co-faithful edges.Then the subgraph G[J]has a matching M such that M covers both the faithful edges and the vertex set H,and that M misses every unfaithful vertex.

Proof.We proceed according to the numberxof faithful edges.The casex=3 is Lemma 3.2.

Whenx=2,letbe the unfaithful edge,wherej∈[2n].Assume that the vertexqj-1is uncovered by the matchingM0.By Lemma 3.2,the 3-matchingcan be extended to a matchingM1,which covers the setH.Then the matchingM1-qj-1qjis a desired one.For the same reason,Lemma 3.3 holds true if the vertexqj+1is uncovered byM0.Now,we can suppose that both the verticesqj-1andqj+1are covered byM0.By Lemma 3.2,the matching

can be extended to a matching,say,which covers the setH.Since all the three neighborsqj-1,qj+1andhj,of the vertexqjin the subgraphG[J],are in the matchingM2which misses the vertexqj,we infer that the unfaithful vertexqjis not covered byTherefore,is a desired one.

Whenx=1,we can represent the matchingM0as

where 1≤j＜k≤2n.If the verticesqjandqkare not adjacent in the subgraphG[Q],then there exist two distinct verticesuandwsuch that

By Lemma 3.2,the matching{uqj,wqk,e1}can be extended to a matching,say,M′3,which covers the setH.Then the matchingM′3-uqj-wqkis a desired matching.Otherwise,the verticesqjandqkare adjacent.By Lemma 3.2,the 2-matching{qjqk}∪{e1}can be extended to a matching,say,M′4,which covers the setH.Then the matchingM′4-qjqkis a desired matching.

Whenx=0,the vertex setQcontains exactly three unfaithful vertices.Letqjbe a vertex inQwhich is not unfaithful.LetM5be the perfect matching of the pathH-hjof ordern-1.Then,the matchingM5∪{qjhj}is a desired matching.This completes the proof of Lemma 3.3.

Now we deal with the first casez=0.LetMbe the matching obtained from Lemma 3.3.LetM′be the matching of the subgraphG[J′]which is symmetric toM.In other words,an edgeis in the matchingM′if and only if the edgehihi+1(resp.hjqj,qjqj+1)is inM.Then the set

is a perfect matching of the graphGwhich covers the matchingM0,as desired.

Next lemma is for the case(x,y,z)=(1,1,1).

Lemma 3.4.For any edge e in the subgraph G[J],and for any vertex qkin the set Q-V(e),the subgraph G[J]-V(e)-qkhas a perfect matching.

Proof.It suffices to find a matchingMof the subgraphG[J]-V(e)-qk,such that

1.the pathG[H]-V(M)-V(e)is of even order;

2.every path component of the subgraphG[Q]-V(M)-V(e)-qkis of even order.Below we will construct such a matchingMaccording to the position of the edgee.

Case 1.IfV(e)?H,we can suppose thate=h0h1without loss of generality,and take the matching

Case 2.IfV(e)∩H/=?andV(e)∩Q/=?,then we can suppose thate=h1q1without loss of generality,and take the matching

Case 3.IfV(e)?Q,then we can supposee=q0q1without loss of generality,and take the matching

This completes the proof.

Now we are ready to solve the casex=y=z=1.By Lemma 3.4,the subgraphG[J]-V(M0)has a perfect matching.For the same reason,the subgraphG[J′]-V(M0)has a perfect matching.The union of these two matchings and the matchingM0form a desired perfect matching of the graphG.

For the last case(x,y,z)=(2,0,1),we will need the following lemma.

Lemma 3.5.Let e0be an edge of the subgraph G[Q].Then any2-matching of the subgraph G[J]can be extended to a near perfect matching of G[J],which covers the vertex set H∪V(e0).

Proof.Let{e1,e2}be a 2-matching of the subgraphG[J].It suffices to show that the subgraph

has a matchingMsuch that

1.every path component of the subgraphG[H]-V(e1∪e2∪M)is of even order;

2.at most one of the path components of the subgraphG[Q]-V(e1∪e2∪M)is of odd order;

3.if the subgraph

has an isolated vertex,then the isolated vertex is not an end of the edgee0.

If such a matchingMexists,then the subgraphG[Q]-V(e1∪e2∪M)has a near perfect matchingM′,such that the matchingM∪M′∪{e1,e2}covers the setV(e0).The desired result follows immediately.Below we will seek the above matchingM.According to the positions of the edgese1ande2,we have six cases to treat.

Case 1.Both the edgese1ande2are from the subgraphG[H].The subgraphG[H]-V(e1∪e2)consists of two paths of different parities of orders,in which the path of even order might be empty.Lethibe an end of the path of odd order.We can take the matchingM={hiqi}.

Case 2.The edgee1is from the subgraphG[H],and the edgee2=hjqjfor somej∈[2n].We can suppose thate1=h0h1without loss of generality.Then we can take the matching

Case 3.The edgee1is from the subgraphG[H],and the edgee2is from the subgraphG[Q].Without loss of generality,we can suppose that

where 0≤i≤n-1.Moreover,by symmetry,we can suppose that 0≤i≤(n-1)/2 without loss of generality.We can take the matching

Case 4.Both the edgese1ande2have the formhjqj,wherej∈[2n].Without loss of generality,we can suppose thate1=h1q1.Then we can take the matching

Case 5.The edgee1has the formhjqjfor somej∈[2n],and the edgee2is from the subgraphG[Q].Without loss of generality,we can suppose thate2=q0q1andj∈[n],and take the matching

Case 6.Both the edgese1ande2are from the subgraphG[Q].The subgraphG[Q]-V(e1∪e2)consists of two paths,where one of them might be empty.Since the sum 2n-4 of their orders is even,the two paths have the same parity of orders.Since 2n-4≥6,there is at most one path is of order 1.If such an isolated vertex exists,say,qj,then we can take the matchingMto be the edgehjqj.Otherwise,we can take the matchingMto be the edgehkqk,whereqkis an end of the path of larger order,or an end of any path when the two paths have the same orders.This completes the proof of Lemma 3.5.

The last case(x,y,z)=(2,0,1)can be done as follows.Let

where the edgese1ande2are faithful,and the edgee3is co-faithful.By Lemma 3.5,the subgraphG[J]has a near perfect matchingM1covering{e1,e2},such that the associated uncovered vertexqjsatisfies that its symmetric vertexis uncovered bye3.By Lemma 3.4,the subgraph

has a perfect matchingM2.Hence the matching

is a perfect matching ofGwhich extendsM0.This completes the proof of Theorem 3.3.

Since the bow-tie graphC6??Pncan be embedded onto the Klein bottle,Theorem 3.3 implies immediately that there is an in finite number of 3-extendable graphs which areN2-embeddable.We further propose the following conjecture.

Conjecture 3.1.The graphCm??Pnis 3-extendable for any integersmandnsuch thatmis even.

4 Proof of Theorem 1.2

Recall thatμ′(Σ)is the minimum integerksuch that there is no Σ-embeddablek-extendable non-bipartite graphs.It follows that

This section is devoted to find outμ′(Σ).We will need the following lemma.

Lemma 4.1.Let k≥1.Any connected k-extendable graph of order2k+2is either the complete graph K2k+2,or the complete bipartite graph Kk+1,k+1.

Proof.It is easy to show for the casek=1.Below we letk≥2.LetGbe a connectedk-extendable graph with|G|=2k+2.By Theorem 2.8,either the graphGis bipartite or we haveκ(G)≥2k.

In the former case,any vertex in the part with larger order has degree at most the order of the other part,and thus,at most|G|/2=k+1.By Theorem 2.5,we haveδ(G)≥k+1.Therefore,both parts of the graphGhas orderk+1.Sinceδ(G)≥k+1,we infer thatG=Kk+1,k+1.

In the latter case,we suppose to the contrary that the graphGis not complete.ThenGhas a pair(u,v)of non-adjacent vertices.Since the graphGisk-extendable and is of order 2k+2,we infer that the subgraphG′=G-u-vdoes not have a perfect matching.On the other hand,any graphHof even order withδ(H)≥|H|/2 has a Hamilton circuit;see Ore[13].Since

we deduce that the subgraphG′has a Hamilton circuit,and a perfect matching in particular,a contradiction.This completes the proof.

Now we are in a position to show Theorem 1.2.

Proof.Let Σ be a surface of characteristicχ.Letμ′(Σ)be the minimum integerksuch that every Σ-embeddable non-bipartite graph is notk-extendable.

First,we deal with the sporadic cases thatχ≥-1.For the sphereS0,by Ineq.(4.1),

by Theorem 1.1.On the other hand,it is clear that the graphP4×C5is planar and non-bipartite.Since it is 2-extendable by Theorem 3.1,we deduce thatμ′(S0)=3.

By Ineq.(4.1)and Theorem 1.1,μ′(N1)≤μ(N1)=3.Since every planar graph isN1-embeddable,we deduce thatμ′(N1)≥μ′(S0)=3.Therefore,we conclude thatμ′(N1)=3.

For the torusS1,by Ineq.(4.1)and Theorem 1.1,

On the other hand,it is clear that the graphC6×C5is toroidal and non-bipartite.Since it is 3-extendable by Theorem 3.2,we infer thatμ′(S1)=4.

For the Klein bottleN2,we have

by Theorem 1.1.On the other hand,theN2-embeddable non-bipartite graphC6??P5is 3-extendable by Theorem 3.3.Thusμ′(N2)=4.

Along the same line,we haveμ′(N3)≤4.Sinceμ′(N3)≥μ′(N2)=4,we infer thatμ′(N3)=4.

Below we can suppose thatχ≤-2.Write

Sinceχ≤-2,one may estimate thatn≥4.By Theorem 2.3,it is direct to check thatK2nis Σ-embeddable.It is obvious thatK2nis both(n-1)-extendable and non-bipartite.Thusμ′(Σ)≥n.

Suppose,by way of contradiction,thatμ′(Σ)＞n.Then there exists a the graphG,which is Σ-embeddable,n-extendable,and non-bipartite.Then-extendability implies that|G|≥2n+2.If|G|=2n+2,thenG=K2n+2by Lemma 4.1.By computing the genus and the non-orientable genus ofK2n+2directly,we see thatK2n+2is not Σ-embeddable.Thus we have|G|≥2n+4.

Letvbe a control point in an embedding of the graphGon Σ.Assume that|G|≤4n.By Theorem 2.8,we deduce that the connectivityκ(G)is at least 2n.It follows that

Letxbe the number of triangles containingv.Lety=d(v).Wheny=2n,sinceGisn-extendable,we infer thatx≤2n-2.By Lemma 2.1,

which implies thatχ＞0,a contradiction.Otherwisey≥2n+1.By Lemma 2.1,

which is same to Ineq.(4.3)and thus impossible.

Now we are led to the case that|G|≥4n+2.Assume thatx≤2n-2.By Lemmas 2.1 and 2.2,

Solving the above inequality we find thatχ∈{-6,-5,-4,-3,-2}.Substituting each of these five values ofχinto Ineq.(4.4),we obtain a contradiction.Otherwisex≥2n-1.Then Lemma 2.1 gives

the same contradiction.This completes the proof of Theorem 1.2.

At the end of this paper,we would like to share the approach of finding Eq.(1.2).Our previous result[12]on(n,k)-graphs is as follows.

Theorem 4.1(Lu and Wang).LetΣbe a surface of characteristic χ.Let μ(n,Σ)be the minimum integer k such that there is noΣ-embeddable(n,k)-graphs.Then for n≥1,we have

While Eq.(4.5)was obtained by laborious computations,we discover Eq.(1.2)by the guess-and-check strategy.Although(0,k)-graphs are exactlyk-extendable graphs,Eq.(4.5)is valid under the premisen≥1.Nevertheless,it was Eq.(4.5)by which we were inspired to guess Eq.(1.2)out.

Acknowledgements

The authors appreciate the anonymous referee for his/her careful reading and detailed corrections for improvement.Lu is supported by the National Natural Science Foundation of China(NSFC,Grant No.11871391).Wang is supported by the NSFC(Grant No.12171034)and the Fundamental Research Funds for the Central Universities(Grant No.2021CX11012).He is grateful to the hospitality of Department of Mathematics in MIT.