ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 51-61
Maximum genus, Connectivity, and Nebesky's
Theorem
Dan Archdeacon
Department of Mathematics and Statistics, University of Vermont Burlington, VT, USA 05405
Michal Kotrbcik
Department of Computer Science, Comenius University, 842 48 Bratislava, Slovakia
Roman Nedela
Mathematical Institute, Slovak Academy of Sciences, 975 49 Banskd Bystrica, Slovakia
Martin Skoviera
Department of Computer Science, Comenius University, 842 48 Bratislava, Slovakia Received 19 July 2012, accepted 10 October 2013, published online 20 June 2014
We prove lower bounds on the maximum genus of a graph in terms of its connectivity and Betti number (cycle rank). These bounds are tight for all possible values of edge-connectivity and vertex-connectivity and for both simple and non-simple graphs. The use of Nebesky's characterization of maximum genus gives us both shorter proofs and a description of extremal graphs. An additional application of our method shows that the maximum genus is almost additive over the edge cuts.
Keywords: Maximum genus, Nebesky's theorem, Betti number, cycle rank, connectivity. Math. Subj. Class.: 05C10
1 Introduction
We study cellular embeddings of graphs in orientable surfaces of large genus. Suppose that G is a connected graph with v vertices and e edges embedded with f faces on an orientable surface of genus g, denoted here by Sg. Our goal is to find the maximum genus of G,
E-mail addresses: dan.archdeacon@uvm.edu (Dan Archdeacon), kotrbcik@dcs.fmph.uniba.sk (Michal Kotrbcik), nedela@savbb.sk (Roman Nedela), skoviera@dcs.fmph.uniba.sk (Martin Skoviera)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
52
Ars Math. Contemp. 9 (2015) 115-124
YM(G), which is the maximum value of g over all cellular embeddings of G. The Euler-Poincare formula asserts that v - e + f = 2 - 2g. By combining this formula with the formula fi(G) = 1 - v + e for the Betti number (cycle rank) of G we get f - 1 = fi - 2g. Since the maximum genus g corresponds to the minimum number of faces f and since every embedding has at least one face, f - 1 (or equivalently fi - 2g) measures how far the embedding is from the extreme of only one face. We call this quantity the deficiency £ of the embedding. The deficiency of G, £(G), is the minimum deficiency over all possible embeddings, and so £(G) = fi(G) - 2ym(G). Note that £(G) always has the same parity as fi(G). In particular, an embedding of a graph with odd Betti number always has at least two faces and hence deficiency at least one. A graph with deficiency 0 or 1 is called upper embeddable. For more background on the maximum genus we refer the reader to [3].
In this paper we give lower bounds N on the maximum genus of graphs in various classes C defined by the graph's Betti number and edge-connectivity. The graphs are allowed to have loops and multiple edges; if these are forbidden we say that the graph is simple. Our results can be rephrased as "Every graph in C has an embedding in a surface with at least N handles". We also get analogous results for Betti number and vertex-connectivity. These classes have been examined before [2, 4, 5, 7, 8, 11], nevertheless, we present a unified approach with new, much shorter proofs, providing additional information about the structure of the extremal graphs.
In addition to the bounds on the maximum genus of a graph in terms of its connectivity, we explore the relationship between the maximum genus of a graph and the maximum genera of components resulting from the removal of an edge-cut. By an edge-cut in a graph G we mean a minimal set F of edges that separate two sets of vertices V1 and V2 forming a partition {'V1, V2} of the vertex-set of G; every edge from F has precisely one vertex in each of Vi and V2. We show that the maximum genus of a graph is almost additive over its edge-cuts (in a sense to be made clear in Section 3). We also investigate a related question asking for the smallest size of an edge-cut that can separate a non-upper-embeddable component.
The primary tool used in this paper is Nebesky's Theorem [12], stated below as Theorem 1.1 (or its equivalent version due to Khomenko and Glukhov [9] stated later in Equation 3.4). Let G be a connected graph and let A be a set of its edges. Let oc(G - A) denote the number of components of G - A with odd Betti number and ec(G - A) the number of those with even Betti number. Let
v(G, A) = ec(G - A) + 2oc(G - A) - |A| - 1. Theorem 1.1 (Nebesky [12]). The deficiency of a graph G is given by £(G) = max{v(G, A) : A C E(G)}.
The idea behind Nebesky's Theorem is easy and its understanding is important to this paper. Consider a maximum-genus embedding of G with f faces. Delete the edges of A one at a time. If deleting an edge increases the number of components, then we embed each new component on its own connected surface. With this convention, deleting an edge can increase the total number of faces, but by at most one. Hence the embedding of G - A has at most f + |A| faces. If a component of G - A has odd Betti number, then its surface has at least two faces. If the Betti number is even, then its surface has at least one face. It follows that f + |A| > ec(G - A) + 2oc(G - A), and so £(G) = f - 1 > v(G, A). Nebesky's Theorem also asserts that there is a set A of edges in a maximum genus embedding that reverses the steps just described; the proof in this direction is more difficult.
Dan Archdeacon et al.: Maximum genus, connectivity, and Nebesky's Theorem
53
Previous results relating maximum genus, connectivity, and the Betti number mostly used Xuong's Theorem [15] to determine the maximum genus. It is our use of Nebesky's alternative characterization [12] that gives us new insights and shorter proofs; these techniques were first introduced in an earlier unpublished version of this paper (1996).
2 Graphs with given connectivity
In this section we state and prove our results giving upper bounds on the deficiency of graphs with a particular Betti number and connectivity. We then translate these results to give lower bounds on the maximum genus. We need several observations before proceeding.
First, note that if G has a vertex v of degree one, then yM (G - v) = yM (G). If v is of degree two, then we can replace its two incident edges with a single edge joining the other two incident vertices. This does not change the maximum genus, but can turn a simple graph into a non-simple one. Since simple and non-simple graphs behave differently, the statements of our results are cleaner if we forbid degree two vertices. Hence we require that our graphs are of minimum degree at least three.
The proofs involve calculating v(G, A) and bounding 8(G) from below. Different types of components in G - A will play different roles. Let c0 = c0(G - A) be the number of components in G - A with Betti number zero. Let c1 denote those components with Betti number one. Let c2 be the number of components with even Betti number at least 2, and c3 be the number of components with odd Betti number at least 3. With this notation observe that
v(G, A) = co + 2ci + C2 + 2c3 - |A| - 1.	(2.1)
To bound the Betti number of G, first note that G - A has components whose Betti numbers sum to at least c1 + 2c2 + 3c3. Adding in c0 + c1 + c2 + c3 - 1 edges from A, we can build a connected graph whose Betti number is also at least c1 + 2c2 + 3c3. Adding the remaining edges in A increases the Betti number by |A| - (c0 + c1 + c2 + c3 - 1). Hence
8(G) >-co + c2 + 2c3 + |A| + 1.	(2.2)
We are now ready for the first version of our main result.
Theorem 2.1. Let G be a graph of minimum degree at least three. Then upper bounds on the deficiency £(G) are given in following table. The rows correspond to edge-connectivity k =1,2,3, or > 4. The same bounds hold where k is the vertex-connectivity and are achieved by graphs of arbitrarily large Betti number.
k	simple	non-simple
1 2 3 > 4	(8(G) - 2)/2 (8(G) = 3) 08(G) - 4)/3 (¡(G) = 3, 5) (8(G) - 4)/3 (8(G) =3, 5) 1	8(G) 8(G) - 2 (8(G) - 4)/3 (8(G) =3, 5) 1
Proof. We prove the upper bounds for k-edge-connected graphs G. Since k-vertex-con-nected implies k-edge-connected, the bounds also hold for vertex-connectivity. We achieve
54
Ars Math. Contemp. 9 (2015) 115-124
the bounds with k-vertex-connected graphs, so the bounds are best possible in both cases. The proof has five main cases.
Case (i). We begin with possibly non-simple graphs having edge connectivity (or vertex connectivity) k > 4. First observe that v (G, 0) is 0 when P(G) is even and is 1 when P(G) is odd. We will show that no 4-edge-connected G has a non-empty subset A with v(G, A) > 0. As a consequence, any such graph is upper-embeddable and the bounds in our table are best possible. This result has been noted by many authors, usually using Kundu's Theorem [10] combined with Xuong's Theorem [15].
To establish the inequality, first note that if A is non-empty and G-A is connected, then v(G, A) < 0. If G - A is disconnected, then each component of G - A is incident with at least4 edges in A. Counting edge ends and dividing by 2 we get |A| > 2c0+2ci+2c2+2c3. Substituting in Equation 2.1 gives v(G, A) < — c0 - c2 - 1 < 0 as desired.
Case (ii). We next consider graphs that are either 3-edge-connected and non-simple or 2-edge-connected and simple. The bound for simple graphs was first shown in [2].
Let A be a non-empty subset of edges. We need to show that v(G, A) < (P(G) - 4)/3. Substituting Equation 2.1 for v(G, A), Equation 2.2 for P(G), and simplifying, it suffices to show that
If G is 3-edge-connected, then every component is incident with at least three edge-ends from A. Hence 2|A| > 3(c0 + c1 + c2 + c3) implying Equation 2.3. The bound is achieved if and only if c0 = c2 = c3 = 0.
If G is 2-edge-connected and simple, then every component of G - A contributing to c0 is incident with at least 3 edges (by minimum degree at least 3). A component contributing to c1 is incident with at least 3 edges by simplicity. The remaining components are incident with 2 edges by connectivity. Hence 2|A| > 3c0 + 3c1 + 2c2 + 2c3. Again, Equation 2.3 is shown and the bounds follow. The bound is achieved if and only if c0 = c2 = 0, every component contributing to c1 is a triangle and every component contributing to c3 is incident with precisely 2 edges from A.
If A is an empty set of edges, then v(G, A) = 0 or 1, depending on whether P(G) is even or odd respectively. This is less than (P(G) - 4)/3 unless P(G) = 3 or 5, hence the two excluded cases.
One way to achieve the above bound is to replace every vertex of a 3-connected simple graph with a triangle so that every vertex is of degree three. Here the set A corresponds to all of the original edges in the graph. This example shows that the bound is best possible in both classes.
Case (iii). The next case is when G is simple and connected, first done in [4]. As before, we need to show that v(G, A) < (P(G) - 2)/2 for every pair (G, A). Again substituting in Equations 2.1 and 2.2, it suffices to show that
Our goal is to show that there is a pair (G, A) minimizing p with a certain structure, allowing us to show that p(G, A) > 0. We start by choosing a pair (G, A) minimizing p(G, A) where A is minimal with respect to inclusion, and proceed by proving several claims about (G, A).
2|A| > 2co + 3ci + c2 +2c3.
(2.3)
p(G, A) := 3|A| - (3co + 4ci + C2 + 2C3) + 1 > 0.
(2.4)
Claim 1: Every edge from A joins two distinct components of G - A.
Dan Archdeacon et al.: Maximum genus, connectivity, and Nebesky's Theorem
55
If there were an edge x such that both ends of x are incident with a single component of G — A, then ^(G, A — {x}) < ^(G, A), which contradicts the minimality of A.
Claim 2: Each component of G — A has odd Betti number.
To see this, first note that c0 = 0. If not, we could replace an acyclic component with a cycle of suitable length incident with the same edges of A as the original component to obtain a simple graph G' with minimum degree at least 3. For the resulting pair (G', A) we have m(G', A) < ^(G, A), which contradicts the minimality of We further observe that c2 = 0. If not, we could replace a component contributing to c2 with a suitable subdivision of K4 contributing to c3. This can always be done in such a way that the resulting graph G' is simple and has minimum degree at least 3. However, ^(G', A) < ^(G, A), again contradicting the minimality of
Claim 3: No component of G — A is incident with exactly two edges of A.
Suppose there were such a component C, and let e, f denote the edges from A incident with C. As shown above, fi(C) is odd, and since G is simple and has minimum degree at least three, fi(C) > 3. Consider a pair (G', A') constructed by deleting C from G and joining the other ends of the edges incident with C. It is not difficult to see that G' has minimum degree at least three and that m(G', A') < ^(G, A); however, the graph G' may not be simple. If the graph G' is simple, then ^(G', A') < ^(G, A) contradicts the minimality of If G' is not simple, then we distinguish two cases: e and f join C with either one or two components of G — A.
If there is one component, it can contribute to ^ by at most 4. It follows that ^(G, A — {e, f}) < m(G, A), contradicting the minimality of A.
If there are two components call them D1 and D2. Then joining the ends of e and f in G creates a pair of parallel edges in G'. Moreover, this implies that D1 and D2 are joined by some edge in A, say g. As both D1 and D2 can contribute to ^ by at most 4 and C contributes by 2, it follows that ^(G, A — {e, f, g}) < ^(G, A), again contradicting the minimality of A.
Claim 4: A component C of G — A has fi(C) = 1 if and only if it is incident with at least three edges of A.
Let C be a component of G — A incident with at least three edges. If fi(C) > 3, then we can replace it with a cycle of suitable length to obtain a simple graph G' with minimum degree at least 3. For the resulting pair (G', A') we again have m(G', A') < ^(G, A), a contradiction. If D is a component incident with just one edge of A, then the simplicity and the minimum degree of G guarantee that fi(D) > 3. This proves Claim 4.
Having established some properties of G — A, we return to the proof of Case (iii). Form the graph H = G/(G — A) from G by contracting each component of G — A into a vertex. Note that |E(H) | = |A| and that H has no vertices of degree 2. As H is connected, |E(H)| > c1 + c3 — 1. Denote the number of vertices of degree 1 in H by v1 and the number of vertices of degree at least 3 by v3. Observe 2|E(H)| > 3v3 + v1 = 3c1 + c3. By adding the two inequalities we get 3|E(H)| = 3|A| > 4c1 + 2c3 — 1. Substituting this into (2.4) yields
M(G, A) = (4c1 + 2c3 — 1) — (4c1 + 2c3) + 1=0.
56
Ars Math. Contemp. 9 (2015) 115-124
To achieve the bound (P(G) - 2)/2 > v(G, A), start with any tree H having only vertices of degree 1 or 3. Replace each degree three vertex with a triangle and each degree one vertex with a copy of K4 (possibly with one edge subdivided) so that every vertex has degree at least three.
Case (iv). We next turn to the case where G is non-simple and 2-edge-connected. Every component is incident with at least two edges in A, so | A| > c0 + ci + c2 + c3. This gives v(G, A) < c1 + c3 - 1 and P(G) > c1 + 2c2 + 3c3 + 1. To maximize v with an upper bounded P we must have c2 = c3 = 0. Hence v(G, A) < P(G) - 2, giving another entry in our table. This bound is achieved by the graph formed by replacing every other edge of the cycle C2n with two edges in parallel. These graphs are the necklaces of [2].
Case (v). When G is non-simple and 1-edge-connected we have |A| > c1 + c2 + c3 - 1. This gives v(G, A) < P(G) as desired. The bound is achieved by duplicating every other edge on a path with an even number of edges and contracting one of the two edges incident with a vertex of degree two. Complete characterization of non-simple 1-edge-connected graphs achieving this bound can be found in [13].
We have completed filling in the table and the proof of our theorem.	□
Recall that for a graph G embedded in the surface Sg, we have f - 1 = P(G) - 2g, and hence £(G) = P(G) - 2ym (G). We use this formula to translate the upper bounds on £ to lower bounds on the maximum genus ym , giving the following second form of our main result.
Theorem 2.2. Let G be a graph of minimum degree at least three. Then lower bounds on the maximum ym (G) are given in following table. The rows correspond to edge-connectivity k = 1,2,3, or > 4. The same bounds hold where k is the vertex-connectivity and are achieved by graphs of arbitrarily large Betti number.
k	simple	non-simple
1	(P(G) + 2)/4 (P(G) = 3)	0
2	(P(G) + 2)/3 (P(G) = 3, 5)	1
3	(P(G) + 2)/3 (P(G) = 3, 5)	(P(G) + 2)/3 (P(G) = 3, 5)
> 4	(P(G) - 1)/2	(P(G) - 1)/2
□
We note that our table is slightly different than the one in [2] where, for example, they give the lower bound \P (G)/3] for the maximum genus of 2-edge-connected simple graphs of minimum degree at least 3. Both bounds are tight. They are achieved only for graphs with P(G) congruent to one modulo three, when the bounds are the same.
3 Edge-cuts
We now investigate the relationship between the deficiency of a graph and the deficiency of components resulting from the removal of an arbitrary edge-cut. Our motivation is twofold. First, the assumptions concerning arbitrary edge-cuts are much weaker than the connectivity requirements used in Section 2. Second, similar ideas were pursued by Jaeger, Payan,
Dan Archdeacon et al.: Maximum genus, connectivity, and Nebesky's Theorem
57
and Xuong [6] who proved that, under natural parity conditions, a graph that can be separated by an edge-cut into two upper-embeddable components is itself upper-embeddable. Our aim is to generalize this result by replacing upper-embeddability with an arbitrary deficiency. The resulting lower bound for deficiency suggests the following question: "What is the minimum size of an edge-cut that can separate a non-upper-embeddable component in a k-edge-connectedgraph for k > 4?" Our final result, Theorem 3.4, answers this question.
As in the previous section, a crucial role is played by various types of components depending on their Betti numbers. Let F be a fixed edge-cut of a connected graph G with components Gi and G2. Let A be an arbitrary subset of edges of G. We distinguish between two types of components of G - A: a pure component has its vertices entirely in G1 or entirely in G2, while a mixed component is incident with vertices in both. Let d0 denote the number of mixed components of G - A with even Betti number. Let d1 denote the number of pure components of G - A with even Betti number and with vertices from G1. Define d2 similarly for pure components with vertices from G2. Finally, let d3, d4, and d5 denote the odd counterparts of d0, d1, and d2, respectively. Notice that pure components contribute to d1; d2, d4, and d5 and mixed components contribute to d0 and d3.
With this notation, Theorem 1.1 implies the following:
£(G) > v(G, A) = ec(G - A) + 2oc(G - A) — |A| — 1
= do + d1 + d2 + 2d3 + 2d4 + 2d5 - |A| - 1.	(3.1)
We now proceed to the main result of this section, Theorem 3.1. To show that the bounds stated in it are tight we need one more ingredient, Xuong's Theorem [15]: The deficiency of a graph G equals the minimum number of components with odd number of edges (which we call odd for short) in the subgraph G - E (T), where the minimum is taken over all spanning trees T of G.
Theorem 3.1. Let G be a connected graph and let F be an edge-cut such that G - F has precisely two components G1 and G2. Then
£(G1) + £(G2) - |F| + 1 < £(G) < £(G1) + £(G2) + 1,
both bounds being tight. Equivalently,
YM(G1) + YM(G2) + |F|/2 - 1 < YM(G) < YM(G1) + ym(G2) + |F| - 1.
Proof. First we show that £(G) < £(G1) + £(G2) + 1. Let A be some set of edges of G maximal with respect to inclusion such that £(G) = v(G, A). Set Aj = A n E(Gj) for i € {1, 2} and note that
A - (A1 U A2) = A n F.	(3.2)
Our goal is to bound the values of v(G1, A1) and v(G2, A2). Pure components are also components of either G1 - A1 or G2 - A2. Therefore, a pure component contributing to d1 or d2 increases the value of v(G1, A1) or v(G2, A2) by precisely 1. Pure components contributing to d4 or d5 increase the value of v(G1, A1) or v(G2, A2) by precisely 2.
If D is a mixed component, then D - F has at least one component contained in G1 and at least one component contained in G2. Therefore D increases v(G1, A1) + v(G2, A2) by at least 2. Note that if P(D) is even (that is, if D contributes to d0), then D increases v(G, A) only by one. It follows that
ec(G1, A1) + 2oc(G1, A1) + ec(G2, A2) + 2oc(G2, A2) > 2d0 + d1 + d2 + 2d3 + 2d4 + 2d5.	(3.3)
58
Ars Math. Contemp. 9 (2015) 115-124
Combining (3.1), (3.2), and (3.3) we get
£(Gi) + £(G2) > v(Gi, Ai) + v(G2, A2) = ec(G1 ,A1) + 2oc(G1,A1) - |A11- 1 +
ec(G2, A2) + 2oc(G2, A2) - |A21 - 1 > 2do + d1 + d2 + 2d3 + 2d4 + 2d5 - | A11 - |A21 - 2
= ec(G - A) + 2oc(G - A) + d0 - |A11 - |A21 - 2 = ec(G - A) + 2oc(G - A) - |A| - 1 + d0 + |A - (A1 U A2)| - 1 = ^(G) - 1 + |F n A| + do > ^(G) - 1.
This establishes the upper bound on £(G).
To prove the lower bound, for i e {1, 2} let Aj denote a set of edges of Gj maximal with respect to inclusion such that v(Gj, Aj) = ^(Gj). Set A = A1U A2 U F and calculate:
£(G) > v(G, A) = ec(G - A) + 2oc(G - A) - |A| - 1 = ec(G1 - A1) + ec(G2 - A2) + 2oc(G1 - A1) +
2oc(G2 - A2) - |A1| - |A2| - |F|- 1 = v(G1, A1) + v(G2, A2) - |F| + 1 = e(G1) + £(G2) - |F| + 1.
This establishes the lower bound on £(G).
To see that both bounds are tight, take two copies of the dipole Dn, which has two vertices and n parallel edges, and join the copies by two independent edges e and f. Let G be the resulting graph. Using Xuong's Theorem it is easy to verify that £(Dn) = 1 if n is even, £(Dn) = 0 if n is odd, and that £(G) = 1. Let F = {e, f} and let G1 and G2 be the components of G - F. Then £(G) = £^1) + £(G2) - |F| + 1 if n is even, and £(G)= C(G1) + C(G2) + 1 if n is odd.	□
Theorem 3.1 and the fact that £(G) and ft(G) have the same parity give a shorter proof for the following result of Jaeger, Payan, and Xuong [6].
Corollary 3.2. Let G be a connected graph and let F be an edge-cut of G such that G - F has precisely two components G1 and G2, both upper-embeddable. Then G is upper-embeddable provided that both ft(G1) and ft(G2) are even, or precisely one of ft(G1) and ft(G2) is even and ft(G) is odd.	□
In the final part of the proof of Theorem 3.1 we have shown that the lower bound on £(G) is tight in the class of 2-edge-connected graphs. Our next example shows that the lower bound is tight also in the class of 3-edge-connected graphs.
Example 3.3. We construct a rich infinite family of 3-edge-connected graphs G containing an edge-cut F whose removal produces two components G1 and G2 such that £(G) = C(G1) + £(G2) - |F| + 1. Recall that the truncation of a cubic graph H is a cubic graph t(H) obtained by expanding every vertex of H into a triangle.
Let us start with connected cubic graphs H1 and H2 without loops, of order n1 and n2, respectively, both greater than 2. Take their truncations G1 = t(H1) and G2 = t(H2), and connect G1 to G2 by a set F = {f0, f1, f2} of three edges arbitrarily. Let G be the resulting graph; it is easy to see that if H1 and H2 are 3-edge-connected, so is G. Bouchet [1] proved
Dan Archdeacon et al.: Maximum genus, connectivity, and Nebesky's Theorem
59
that £(Gj) = nj/2 - 1 (see [14, Theorem 3.3] for a different proof). We now show that £(G) = £(Gi) + ^(G2) - 2 = £(Gi) + ^(G2) - |F| + 1 = (ni + n2)/2 - 4.
For i g {1, 2} let Aj be the set of edges of Gj not lying in a triangle, and let A = Ai U F U A2. Since |A| = 3 + 3(ni + n2)/2 and G - A consists of ni + n2 triangles, Nebesky's Theorem implies that £(G) > v(G, A) = 2(ni + n2) - 3(ni + n2)/2 - 3 -1 = C(G1) + £(G2) - 2. To prove the reverse inequality, we take in each Hj a spanning tree Sj such that all components of Hj - E(Sj) are paths; it is not difficult to see that this choice is indeed possible [14, Theorem 3.1]. Extend Sj to a spanning tree Tj of Gj by including in Tj two edges from each triangle of Gj. This can be done in such a way that a component of Hj - E(Sj), which is a path of length m > 0, becomes a path of length 2m +1 constituting a component of Gj - E(Tj). A straightforward calculation reveals that there are nj/2 - 1 such components in Gj - E(Tj), all other components being isolated vertices. In particular, Gj -E(Tj) has nj/2 -1 = ^(Gj) odd components. Form a spanning tree T of G by adding the edge /0 to Ti U T2. Clearly, T is also a spanning tree of G' = G - {fi, f2} and the corresponding cotree has (ni + n2)/2 - 2 = ^(Gi) + £(G2) = £(G') odd components. We now add /i and /2 to G' one by one and modify T, if necessary, each time absorbing one odd component.
Pick /i and note that each of its end-vertices belongs to a component Pi of Gi - E(Ti) or a component P2 of G2 - E(T2). Clearly, Pi U {/i} U P2 is a component of (G' + /i) -E(T). If Pi and P2 have different parity, then Pi U {/i} U P2 is even, implying that the cotree (G' + /i) - E (T) has £(Gi) + £(G2) - 1 odd components. If both Pi and P2 are odd, then Pi U{/i}U P2 is an odd component of (G' + /i) - E(T) and therefore the cotree (G' + /i) - E(T) has ^(Gi) + £(G2) - 2 + 1 odd components. It remains to consider the case where Pi and P2 are both even. Let v be the end-vertex of /i in Gi, and let K be the triangle of Gi containing v. The construction of Ti implies that Pi coincides with v and that both edges of K incident with v belong to Ti; take one of them, say k. The third edge of K, denoted by q, belongs to Gi-E(Ti), and the component P of Gi-E(Ti) containing it is an odd path. Note that P - q consists of two even paths, possibly trivial. It follows that T' = T + k - q is a spanning tree of G' + /i such that the component of (G' + /i) - E(T') containing /i is no more odd. Hence, the cotree (G' + /i) - E(T') has ^(Gi) + ^(G2) - 1 odd components, which in turn implies that £(G' + /i) < ^(Gi) + ^(G2) - 1.
To finish the proof that £(G) < C(Gi) + C(G2) - 2 we add /2 to G' + /i and proceed similarly, except that we modify T2 instead of T\.	■
We next turn our attention to 4-edge-connected graphs. Our next result exhibits a dramatic change in the behavior with regard to the smallest size of an edge-cut that can separate a component with large deficiency: the size of an edge-cut that separates a component with deficiency m must be at least linear in m.
A leaf of a graph is a 2-edge-connected subgraph maximal with respect to inclusion. For a graph H, let ol(H) denote number of leaves of H with odd Betti number. The following equivalent version of Nebesky's theorem holds for every connected graph G (see [9]):
£(G) = max{ol(G - A) - |A| : A C E(G)}.	(3.4)
Theorem 3.4. Let G be a k-edge-connected graph with k > 4 and let F be an edge-cut of G whose removal produces a component with deficiency at least m. Then
|F| > (k - 2)m + 2.
60
Ars Math. Contemp. 9 (2015) 115-124
Proof. Let H be a component of G - F with £(H) > m. Each edge of F has at most one end in H. Choose a subset A C E(H) such that £(H) = ol(H - A) - |A| and let l = ol(H - A). As G is k-edge-connected, every leaf from H - A must be incident with at least k edges in G. These edges can be only from F, from A, or they can be bridges of H - A. There are l - 1 bridges in H - A. It follows that
kl < |F| +2(l - 1) + 2|A|.	(3.5)
By substituting l - £(H) for |A| in (3.5) and manipulating the resulting expression we derive
|F| > 2£(H) + l(k - 4)+ 2.
For k = 4 we get
|F| > 2£(H) + 2 = (k - 2)£(H) +2 > (k - 2)m + 2,
as required. If k > 5, then k - 4 > 1, and using the fact that l > £(H) we obtain
|F| > 2£(H) + l(k - 4)+ 2 > 2£(H) + £(H)(k - 4) + 2 > (k - 2)£(H) + 2 > (k - 2)m + 2.
This again gives the required inequality.	□
The following corollary follows directly from Theorem 3.4.
Corollary 3.5. If G is a k-edge-connected graph with k > 4 and F is an edge cut of G such that a component of G - F is not upper-embeddable, then |F | > 2k - 2.	□
Let G be a 4-edge-connected graph and let F be an edge-cut separating it into components Gi and G2. Assuming that m = £(Gi) > £(G2), Theorem 3.4 implies that |F| > (k - 2)m + 2 > 2m + 2. Therefore, ^(G1) + £(G2) - |F| + 1 is always negative and the lower bound in Theorem 3.1 cannot be achieved for 4-edge-connected graphs.
Acknowledgements. The research reported in this paper was supported from the following sources. The second author was partially supported by UK/217/2012 and by VEGA 1/1005/12, the third author was partially supported by APVV-0223-10, and the fourth author was partially supported by APVV project ESF-EC-0009-10 within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation. The authors would like to thank Jianer Chen, Yuangqiu Huang, Saroja Kanchi, Deming Li, and Yanpei Liu for fruitful discussions, and an anonymous reviewer for helpful comments.
References
[1]	A. Bouchet, Genre maximum d'un A-graphe, in: Problèmes combinatoires et théorie des graphes, Colloques Internat. C. N. R. S., Paris, 1978, 57-60. (in French)
[2]	J. Chen, D. Archdeacon and J. L. Gross, Maximum genus and connectivity, Discrete Math. 149 (1996), 19-29.
[3]	J. Chen and Y. Huang, Maximum genus, in: Topics in topological graph theory, 34-44, Encyclopedia Math. Appl. 128, Cambridge Univ. Press, Cambridge 2009.
Dan Archdeacon et al.: Maximum genus, connectivity, and Nebesky's Theorem
61
[4]	J. Chen, S. P. Kanchi and J. L. Gross, A tight lower bound on the maximum genus of a simplicial graph, Discrete Math. 156 (1996), 83-102.
[5]	Y. Huang, The maximum genus on a 3-vertex-connected graph. Graphs Combin. 16 (2000), 159164.
[6]	F. Jaeger, C. Payan and N. H. Xuong, A class of upper-embeddable graphs. J. Graph Theory 3 (1979), 387-391.
[7]	S. P. Kanchi and J. Chen, A tight lower bound on the maximum genus of a 2-connected simplicial graph, manuscript (1992).
[8]	S. P. Kanchi and J. Chen, Simplicializing a 3-connected graph: on lower bounds for maximum genus, manuscript (1992).
[9]	N. P. Khomenko and A. D. Glukhov, Single-component 2-cell embeddings and maximum genus of a graph, in: Some topological and combinatorial properties of graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1980, 5-23. (in Russian)
[10]	S. Kundu, Bounds on number of disjoint spanning trees, J. Combin. Theory Ser. B 17 (1974), 199-203.
[11]	D. Li and Y. Liu, A tight lower bound on the maximum genus of a 3-connected loopless multigraph, Appl. Math. J. Chinese Univ. Ser. B 15 (2000), 369-376.
[12]	L. Nebesky, A new characterization of the maximum genus of a graph, Czechoslovak Math. J. 31 (1981), 604-613.
[13]	E. A. Nordhaus, R. D. Ringeisen, B. M. Stewart, and A. T. White, A Kuratowski-type theorem for the maximum genus of a graph, J. Combin. Theory Ser. B 12 (1972), 260-267.
[14]	M. Skoviera, The decay number and the maximum genus of a graph, Math. Slovaca 42 (1992), 391-406.
[15]	N. H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory B 26 (1979), 217-225.