IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1155
ISSN 2232-2094
BIPARTIZING FULLERENES
Zdenek Dvorak Bernard Lidicky Riste Skrekovski
Ljubljana, June 24, 2011
Zdenek Dvorak Bernard Lidicky* Riste Skrekovski§
lO lO
o
£
CO CO
CO CD
Bipartizing fullerenes^
June 23, 2011
Abstract
A fullerene graph is a cubic bridgeless planar graph with twelve 5-faces such that all other faces are 6-faces. We show that any fullerene graph on n vertices can be bipartized by removing O(y/n) edges. This bound is asymptotically optimal.
Keywords: Fullerene graph; Fullerene stability; Bipartite spanning subgraph
1 Introduction
Fullerenes are carbon-cage molecules comprised of carbon atoms that are arranged on a sphere with pentagonal and hexagonal faces. The icosahedral C60, well-known as Buckminsterfullerene was found by Kroto et al. [10], and later confirmed by experiments by Kratchmer et al. [9] and Taylor et al. [12].
*	Supported by a CZ-SL bilateral project MEB 091037 and BI-CZ/10-11-004. t Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles
University, Malostranske namestl' 25, 118 00 Prague, Czech Republic. E-mail: rakdver@kam.mff.cuni.cz. Partially supported by Institute for Theoretical Computer Science (ITI), project of Ministry of Education of Czech Republic, and ERC starting grant CCOSA (grant agreement no. 259385).
*	Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranske namestl 25, 118 00 Prague, Czech Republic. E-mail: bernard@kam.mff.cuni.cz.
§ Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia. E-mail: skrekovski@gmail.com. Partially supported by ARRS, Research Program P1-0297.
a

Since the discovery of the first fullerene molecule, the fullerenes have been objects of interest to scientists all over the world.
From the graph theoretical point of view, the fullerenes can be viewed as cubic 3-connected graphs embedded into a sphere with face lengths being 5 or 6. Euler's formula implies that each fullerene contains exactly twelve pentagons, but provides no restriction on the number of hexagons. In fact, it is not difficult to see that mathematical models of fullerenes with precisely a hexagons exist for all values of a with the sole exception of a = 1. See [3, 5, 6, 11] for more information on chemical, physical, and mathematical properties of fullerenes.
The question of stability of fullerene molecules receives a lot of attention. The goal is to obtain a graph-theoretical property whose value influences the stability. Different properties, like the number of perfect matchings [7] or the independence number [4] were considered. The property investigated in this paper is how far the graph is from being a bipartite graph, which was suggested by Doslic [1] and further considered in [2]. Despite of the effort none of the so far considered parameters works in all cases. Hence more research is still needed.
For a plane graph H, let F(H) be the set of the faces of H. Let H be a 00	fullerene graph, and let KH be the weighted complete graph whose vertices
correspond to the 5-faces of H and the weight of the edge joining two 5-faces fi and f2 is equal to the distance from fi to f2 in the dual of H. Let b(H) be the size of the minimum set S C E(H) such that H — S is bipartite. Doslic and Vukicevic [2] proved the following:
CSI CSI
CO
CO
Theorem 1. If H is a fullerene graph, then b(H) is equal to the minimum weight of a perfect matching in KH.
A corollary of the above theorem is a polynomial-time algorithm for finding a set of edges S whose removal makes the graph bipartite.
Doslic and Vukicevic [2] conjectured that b(H) = O(yJ|V(H)|). In fact, they gave the following stronger conjecture.
CO
Conjecture 2. If H is a fullerene graph with n vertices, then b(H) < V12n/5.
The main result of this paper is an upper bound on b(H), confirming the weaker version of the conjecture.
Theorem 3. If H is a fullerene graph with n vertices, then b(H) = O(^n).
a
CD
2
o
2 Proof of Theorem 3
Let H be a fullerene graph. A patch with boundary o is a 2-connected subgraph G C H such that o E F(G) (usually, we consider o to be the outer face of G) and F(G) \ F(H) C {o} (but it is possible for the boundary o to be also a face of G). Let v be a vertex incident with o. If degG(v) = 3, then v is a 3-vertex (with respect to o), otherwise v is a 2-vertex (with respect to o). An edge e incident with o is a 22-edge (resp. a 33-edge) if both vertices incident with e are 2-vertices (resp. 3-vertices) with respect to o. If e is neither a 22-edge nor a 33-edge, then it is a 23-edge. The description D(o) of the boundary o is the cyclic sequence in that A represents a 33-edge, B represents a 22-edge, and a maximal consecutive segment of 23-edges is represented by the integer giving its length. For example, the boundary of the patch consisting of a 5-face and a 6-face sharing an edge is described as BB2BBB2.
Let s(o) and t(o) be the numbers of 22-edges and 33-edges of o, respectively, and let s2(o) be the number of pairs of consecutive 22-edges of o. Let p(G) be the number of 5-faces of G distinct from o. The following lemma relates the number of 22- and 33-edges; a similar relation was derived by Kardos and Skrekovski [8].
Lemma 4. If G is a patch with the boundary o, then s(o) = 6 — p(G) + t(o). Proof. Suppose that the length of o is t. Let n = |V(G)|, m = |E(G)| and
CO
let f be the number of faces of G. Since each edge of G is incident with two faces,
2m = 6(f — p(G) — 1) + 5p(G) + t,
i.e., t = 2m+p(G) + 6 — 6f. Note that the number of 2-vertices is (t + s(o) — t(o))/2, which can be easily seen from the modification of the boundary by adding s(o) and deleting t(o) 3-vertices so that there is no 33-edge or 22-edge. Thus
2m = 3n — (t + s(o) — t(o))/2. Substituting for t, we obtain
o^	o, r i 6 — p(G)+ t(o) — s(o)
3m = 3n + 3f — 6 +
2
By Euler's formula, m = n + f — 2, thus 6 — p(G) + t(o) — s(o) = 0 and the claim of the lemma follows.	□
a
CD
CD
10 10
(a)
0 fi
o
1
CO ^
CO CO
(b)
(c)
m
CD CD
m
u
a
CD fi
Figure 1: A fat worm, a slim worm and the shell.
A patch G with the boundary o is a fat worm if p(G) = 0, the subgraph of G induced by V(G) \ V(o) is a path P, and the edges of E(G) \ E(P) incident with each two consecutive inner vertices of P are not incident to a common face of G. See Figure 1(a). Note that in this case, the description of o is
•	BB2B(2k + 2)BB2B(2k + 2) if P has length 2k + 1 and
•	BB2B(2k + 2)B2BB(2k + 4) if P has length 2k + 2.
We consider the patch with exactly one vertex not incident with o (and boundary BB2BB2BB2) to be a fat worm as well (in this case, P has length 0). The patch G is a slim worm if p(G) = 0, V(G) = V(o) and t(o) = 0. Geometrically, it is a straight line of hexagons, see Figure 1(b). Note that D(o) = BBB(2k)BBB(2k) for some k (or D(o) = BBBBBB, when k = 0 and o is a 6-face). The patch G is a worm if it is a fat worm or a slim worm. The shell is the patch G with boundary o such that p(G) = 0 and D(o) = BB4BB4BB4 (having 4 internal vertices). See Figure 1(c).
An (.-chord of a cycle C in a patch G is a path of length t with distinct endvertices belonging to V(C) such that the inner vertices and edges of the path do not belong to C. We say a chord instead of a 1-chord. Consider an (-chord Q of the boundary o of a patch G. Let Gi and G2 be the two patches
CD
10 10
Figure 2: Two 4-chords.
0 fi
o
1
CO ^
CO CO
m
CD
u
CD
m
u
a
CD U
into that Q splits G (i.e., the subgraphs such that G1 U G2 = G, G1 H G2 = Q and G1 = Q = G2), and o1 and o2 their boundaries. We say that Q splits off a face if G1 = o1 or G2 = o2. The patch G is decomposable if it contains a simplifying cut, that is
•	an £-chord Q of o with £ < 3 such that t(o1) + t(o2) < t(o), or
•	two 4-chords Q1 = v0v1v2v3)v4 and Q2 = w0w1 w2w3w4 such that v0w0, v2w2 and v4w4 are edges of G. See Figure 2.
Otherwise, we call G indecomposable. We say that G is a normal patch if G is indecomposable, no 5-face of G distinct from o shares an edge with o and G is neither a worm nor a shell.
Lemma 5. Let G be a normal patch with boundary o and Q an £-chord of o, with £ < 3. Then £ > 2 and Q splits off a face. Furthermore, the number of 33-edges incident with the endvertices of Q is most £ — 2.
Proof. Let G1 and G2 with boundaries o1 and o2, respectively, be the patches to that Q splits G. Let Q = q0q1... qe and o2 = q0v1v2 ... vaqeqe-1... q0.
Suppose first that £ =1. Since G is not a slim worm, there exists an edge e E E(G) that either is a 33-edge of o or is incident with a vertex in V(G) \ V(o). Let us choose the chord Q and the patches G1 and G2 so that e E E(G2) and G2 is minimal. As G is indecomposable, each 33-edge of G is also a 33-edge in G1 or G2. It follows that v1 and va are 2-vertices, and since the internal face incident with q0v1 has length six, v2 and va-1 must be adjacent. Since e E E(G2), we have G2 = o2; hence, v2va-1 is a chord of o. The chord v2va-1 splits G to patches G1 and G2 with G2 C G2. However,
CD
10 10
0 fi
o
1
CO ^
CO CO
m
CD CD
m
u
a
CD fi
va _ Vg-1 q3
X = V3
qo vi
(a)
qo vi (b)
Figure 3: 3-chords from Lemma 5.
this contradicts the choice of Q, since it is easy to see that e E E(G'). We conclude that o is an induced cycle.
Suppose now that t =2. By symmetry between G1 and G2, we may assume that q1 is a 2-vertex in G2. Since t(o1) + t(o2) > t(o), we have that v1 and va are 2-vertices, and it follows that G2 = o2 is a face split off by Q.
Finally, suppose that t =3. Suppose first that both q1 and q2 are 2-vertices in G2, and thus q1q2 is a 33-edge with respect to o1. Since t(o1) + t(o2) > t(o), at least one of v1 and va (say v1) is a 2-vertex. Thus, V(Q) U {v1,v2,va} are all incident with a common face, which is only possible if v2 = va and G2 consists of a single face. It follows that Q splits off a face.
The case that both q1 and q2 are 2-vertices in G1 is symmetrical. Hence, without loss of generality, we assume that q1 is a 2-vertex and q2 is a 3-vertex in G2. As t(o1) + t(o2) > t(o), we infer that both v1 and va are 2-vertices. Let x E {q1, q3} be the third neighbor of q2. Observe that
•	if x E V(o), then both xq2q3 and xq2q1qo split off a face (for the former, note that the edge joining va-1 with a neighbor of x is not a chord, since we already proved that o is an induced cycle). See Figure 3(a).
•	if x E V(o), then x and v2 are adjacent, v1v2xq2q1q0 is a face and we may apply the same observations to the 3-chord v2xq2q3. See Figure 3(b).
By symmetry, this argument also holds for o1 . Hence by repeating the argument we conclude that G is a fat worm, contradicting the assumption that G is a normal patch.
Furthermore, note that if Q splits off a face, then t(o) = t(o1) + t(o2) — (t — 2) + k, where k is the number of 33-edges incident with q0 or q^. Since
v
a
CD
io io
( S		
' ®-4—m	o'/\	• wp—• ;
(a)
zi
Z2
x (b)
0 fi
o
1
CO ^
CO CO
CO CD
■ i-H
u
CD CO
Jh
a
CD U
Figure 4: Patch G and o' and a configuration from Lemma 6.
G is indecomposable, it follows that k < t — 2.
□
For a patch G with boundary o, let G' C G be the subgraph consisting of the outer layer of the faces of G; that is, e is an edge of G' if and only if it is incident with a face that shares an edge with o. Let S C V(G) \ V(o) be the set of vertices that have at least two neighbors in o. Let d = G' — (V(o) U S). See Figure 4(a).
Lemma 6. If G is a normal patch with boundary o, then o' is a cycle, and the patch bounded by o' satisfies t(o') = t(o), s(o') = s(o) and s2(o') > s2(o). Furthermore, t(o') = t(o) + 2p(G) — 12 — 2s2(o).
Proof. Since G is not a fat worm, we have |V(G) \ V(o)| > 1. If two vertices of S were adjacent, then |V(G) \ V(o)| = 2 by Lemma 5 and G would be a fat worm, thus S is an independent set and o' is not empty. Lemma 5 also implies that G — V(o) is connected, and since S only contains vertices whose degree in G — V(o) is one, o' is connected as well.
Suppose that a vertex w of o' is adjacent to more than one vertex of S. Since G is not the shell, w is adjacent to exactly two vertices in S; let z be the neighbor of w not in S. Since G is not a fat worm, we have z ^ V(o). Let zi and z2 be the neighbors of z distinct from w; since z ^ S, we may assume that z2 ^ V(o). Let f be the face of G incident with w, z and z2, and let x be the neighbor of z2 in f distinct from z. Note that f is incident with a neighbor of w that belongs to S, and thus f shares an edge with o. Hence f is a 6-face and we have x E V(o). If z1 E V(o), then the 3-chord z1zz2x contradicts Lemma 5. Otherwise, by a symmetric argument we conclude that
o
CSI CD
a face f' incident with w, z and z1 is also a 6-face sharing an edge with o, see Figure 4(b). However, f U f' forms a simplifying cut (a pair of 4-chords) in G, which is a contradiction. Therefore, each vertex of o' has at most one neighbor in S.
By Lemma 5, no vertex of o' has a neighbor both in S and in o, since at least one of the two resulting 3-chords would not split off a face. If v is a vertex of o' that has a neighbor in o or S, then v has two neighbors in o', and thus o' has at least three vertices.
Suppose that o' contains a bridge e = uv. Note that both faces fi and f2 of G incident with e share an edge with o. As u, v E S, these two vertices do not lie on 2-chords. Note that f1 U f2 contains an tu-chord Pu of o such that u E V(Pu) and v E V(Pu), where 3 < tu < 5. Similarly, let Pv be an tv-chord of o such that v E V(Pv) and u E V(Pv). As neither Pu nor Pv splits off a face, Lemma 5 implies that tu,tv > 4. Since f1 and f2 are 6-faces, we conclude that Pu and Pv are 4-chords. Lemma 5 further implies that u and v are middle vertices of Pu and Pv, thus f 1 and f2 is a pair of 4-chords forming a simplifying cut. This is a contradiction; therefore, o' is 2-edge-connected. Since o' C G', every edge of o' is incident with a face that shares an edge with o. We conclude that o' is a cycle.
00
Consider now a 33-edge x1x2 in o and let xi^2x3x4x5x6 be the incident 6-face. Lemma 5 implies that each of x3 and x6 has only one neighbor in o, as otherwise one of them would belong to a 2-chord whose endpoint is incident with a 33-edge x1x2. Therefore, x3,x6 E S and x3x4x5x6 is a part of o', and
x4x5 is a 33-edge with respect to o'. It follows that t(o') > t(o).
CO	On the other hand, consider a 33-edge y4y5 of o', and let y3y4y5y6 be a part
of the boundary of o'. As y4 and y5 are 3-vertices in o', there exists a 6-face y1y2y3y4y5ye in G, and y1y2 is a 33-edge in o. Hence, we have t(o') = t(o) and by Lemma 4, s(o') = s(o).
Similarly, consider a part z0z1 z2z3z4z5z6 of o, where z2z3 and z3z4 are 22-edges. The common neighbor z of z1 and z5 belongs to S, and its neighbor z' distinct from z1 and z5 belongs to o'. As we observed before, both neighbors z' and z2 of z' distinct from z belong to o'. Furthermore, by Lemma 5, the endpoints of the 2-chord z1zz5 are incident with no 33-edges, thus z0 and z6 are 2-vertices. It follows that both z' and z2 have a neighbor in o, and z'z' and z2z' are 22-edges with respect to o'. Hence, we conclude that s2(o') > s2(o).
In fact, D(o') can be obtained from D(o) in the following way: Add 0 between each two consecutive letters in D(o). Since endvertices of a 2-
a
CD
CSI CSI

chord of o are not incident with 33-edges, if B0B appears in the resulting sequence, then it is as a part of a subsequence n1 B0Bn2, where n1,n2 > 3. We construct D(o') by CD
•	for each n1B0Bn2 subsequence, decreasing each of n1 and n2 by 3,
•	for each B not contained in such a subsequence, decreasing each of the neighboring integers by 1,
lO
•	for each A, increasing each of the neighboring integers by 1, and
•	suppressing any zeros.
•
Note that the increases/decreases are cumulative, e.g., if D(o) contains a subsequence A3B2B, then the sequence D(o') contains a subsequence A3B0B (or A3BB after suppressing zeros). By Lemma 4, t(o) — s(o) = p(G) — 6, and the formula for the length of oO follows:
= £(o) + 2p(G) — 12 — 2s2(o).
(N
Consider a patch G with boundary o1. A sequence of cycles o1, o2, ..., ok (with k > 2) is called an uninterrupted peeling if for 1 < i < k, the subpatch of G bounded by o* is normal and oi+1 = oi.
CO
CD
■ i-H fi
CD
fi a
CD fi
£(o') = £(o) + 2t(o) — 2(s(o) — 2s2(o)) — 6^2 (o)
Lemma 7. Let o be the boundary of a patch G such that p(G) = 6. If o = o1; o2, ..., ok is an uninterrupted peeling, then the number of vertices of G outside of (and not including) ok is at least 4k2/9.
Proof. By Lemma 6, we have s2(o1) < s2(o2) < ... < s2(ok). Moreover, Lemma 6 also implies that the sequence €(o1),... , €(ok) is concave.
Let a be the largest index such that ^(o1) < ... < €(oa) and let b be the smallest index such that £(ob) > ... > £(ok). Note that if the whole sequence is decreasing then a = b = 1 and similarly if the whole sequence is increasing then a = b = k, hence a < b in all the cases. We compute a lower bound on
the the number of vertices of G outside of ok as
k-1	a-1	b— 1	k-1
£ *(<*) = £ *(<*) + £ €(oi) + £
c^
CD
First, we deal with the middle term. Let m = b — a. Suppose that a < b. In this case, we have £(oa) = £(oa+1) = ... = £(ob); let r = £(oa). By Lemma 6, s2(o^ = p(G) — 6 for a < i < b. Since p(G) = 6, we conclude that s2(oa) > 1. It follows that D(oa) contains a subsequence n1BBn2, where n1,n2 > 3 by Lemma 5. By Lemma 4, t(oa) — s(oa) = p(G) — 6 = s2(oa). As s(oa) > 2s2(oa), we conclude that t(oa) > 3, and thus n1 + n2 + 5 < r. By symmetry, assume that 2n1 < r — 5. As observed in the proof of Lemma 6, D(oa+1) contains a subsequence n'1BBn'2, where n1 < n1 — 2 (the equality is achieved if n1 is adjacent to A in D(oa)). The same observation applies to oa+1, ..., ob-2. In the normal patch ob-1, the integers adjacent to BB are greater or equal to three, thus n1 > 2m + 1 and r > 4m + 7. It follows that £b=a £(o%) = mr > m(4m + 7). In the case that a = b, we have Si—1 £(o») = 0 = m(4m + 7), since m = 0.
Now we deal with the other terms of the sum. If a > 1, then the sequence £(o1),£(o2),... ,£(oa-1) dominates the arithmetic sequence with the first element £(o1) > 5 and step 2 due to Lemma 6 and the fact that p(G) — 6 — s2(oi) > 1 for 1 < i < a — 1. Hence Ja— £(o-) > Ja—1^ + 2i) = (a — 1)(a + 3). If a = 1 then J*-1 £(oi) = 0 = (a — 1)(a + 3).
Similarly, the sequence £(ob), £(ob+1),..., £(ok-1) dominates the arithmetic sequence with the last element £(ok-1) > 7 and step —2, hence £ J—1 £(o») >
CSI
CD W
E-Zr (5 + 2i) = (k — b)(k — b + 6).
Note that (a — 1) + m + (k — b) = k — 1. Summing these inequalities, we obtain
k-1
^ £(o-) > (a — 1)(a + 3)+ m(4m + 7) + (k — b)(k — b + 6)
i=1
>	(a — 1)2 + 4m2 + (k — b)(k — b + 2) + 1
>	4k2/9,
where the lower bound in the last inequality is achieved for a — 1 = 4k/9, k — b = 4k/9 — 1 and m = k/9. Since all the cycles o1, ..., ok-1 are strictly outside of ok, the claim follows.	□
Lemma 8. Let H be a fullerene with n vertices and f a 5-face of H. There exist at least five 5-faces distinct from f whose distance to f in the dual of H is at most v/63n/2 + 14.
Proof. We define a rooted tree T with each vertex of T corresponding to a patch G C H such that p(G) = 0 and p(G) = 6. Furthermore, we assign a
&
CD
c^ c^
weight d(e) to each edge e of T. The root of T is the patch G0 = H whose boundary is the cycle bounding f, i.e., p(G0) = ll. Suppose that a patch G with boundary o is a vertex of T . Let us note that G is neither a worm nor the shell, since p(G) > 0. The sons of G in the tree are defined as follows:
(a)	If p(G) E {l, 7} and o shares an edge with a 5-face of G, then G is a leaf of T.
(b)	If G is a normal patch, then G has a single son G', equal to the last element of the maximal uninterrupted peeling starting with o. The weight of the the edge e joining G with G' is equal to the length (number of patches) of the uninterrupted peeling. Note that G' is not a normal patch.
fi
(c)	If G has a simplifying cut, then let o 1 and o2 be the boundaries of the two patches G 1 and G2 to that it splits G. Note that t(o 1) + t(o2) < t(o). The patch Gi (with i E {l, 2}) is a son of G if p(G^) = 0 and p(G^) = 6. In that case, the edge between G and Gi has weight l. Since 0 < p(G) < 12 and p(G) = 6, G has at least one son.
CSI
(d)	Finally, if G is indecomposable, p(G) E {1, 7} and o shares an edge with a 5-face f', note that there exists an t-chord (with t < 4) splitting
CSI
off f' (otherwise f' would be incident with a chord and a 2-chord and both of them would witness the decomposability of G). We let the son G' of G with boundary o' be the patch obtained from G by removing S	edges incident to both f' and o and by removing isolated vertices. We
let the edge of T between G and G' have weight 1.
The type of G is defined according to the rule ((a) to (d)) in that its sons are described.
Observe that at least five 5-faces distinct from f share edges with boundaries of the patches forming the vertices of T of type (a) or (d). Indeed, either all 5-faces are reachable in this way, or there are exactly six potentially unreachable 5-faces contained in a single patch that is a leaf of T, or split off by a simplifying cut from an internal vertex of T. Let T1 be a subtree of T of smallest possible depth that contains five vertices of type (a) or (d). We choose T1 to be minimal, i.e., all leaves of T1 are of type (a) or (d).
Consider a vertex G1 with a son G2 in T1, and let o1 and o2 be the boundaries of these patches. If G1 is of type (b), then p(G1) = p(G2) and
a
CD
CSI CD
t(o1) = t(o2) by Lemma 6. If G1 is of type (c), then p(G1) > p(G2) and t(o1) > t(o2). If G1 is of type (d), then p(G1) > p(G2) and t(o1) > t(o2) — 1.
Let P = p1p2.. .pm be the path in T joining the root G0 = p1 with a leaf G = pm whose boundary is incident with a 5-face f'. Observe that the distance between f and f' in the dual of G is at most the sum of the weights of the edges of P, plus 1. Let o0 and o be the boundaries of G0 and G, respectively. Let mb, mc and md be the numbers of vertices of types (b), (c) and (d) in P distinct from G, respectively. By the observations in the previous paragraph, we have t(o) < t(o0) + md — mc = 5 + md — mc. By the choice of T1, we have md < 4, and since t(o) is nonnegative, mc < 9. Therefore,
Y d(pipi+1) < mc + md < 13. pi is non-normal
Let d1, d2, ..., dmb be the sequence of the weights of all edges pipi+1 of P such that pi is a normal patch; by the construction of T, pi+1 is not a normal

00 CSI CSI
patch in this case, hence mb < mc + md + 1 < 14. Using Lemma 7, we obtain
4 mb	4 / mb
n > 9 £d2 > 9m (£di i=1 \i=1
Therefore, the total weight of these edges is at most y^63n/2, and the distance between f and f' is at most \j63n/2 + 14.	□
Lemma 9. Every graph G on 12 vertices with minimum degree 5 such that K57 C G has a perfect matching.
Proof. If G does not have a perfect matching, then there exists a set S C V(G) such that G — S has more than |S| components of odd size. Consider such a set S, and observe that |S| < 6. As 5(G) > 5, G is either 2K6 (and thus has a perfect matching) or G is connected. Therefore, | S| > 1.
If |S| < 5, then since 5(G) > 5, no component of G — S may consist of a single vertex, and hence G—S has at most three odd components and |S| < 2. Since 5(G) > 5, each component of G — S has size at least 4. However, G — S must have at least two components of odd size, thus it would have exactly two components of size 5. However, then |S| = 2, which is not smaller than the number of odd components.
Therefore, |S| = 5 and G — S has at least 6 components of odd size. However, this is only possible if each component of G — S consists of a single vertex, and hence K5 7
CG.	□
a	'
CD

Proof of Theorem 3. Let K'H be the subgraph of KH consisting of edges with weight at most ^/63n/2 + 14. By Lemma 8, 8(KH) > 5, and thus K'H either has a perfect matching or K5,7 as a subgraph, by Lemma 9. In the former case, the weight of each perfect matching in K'H (and thus of the minimum-weight perfect matching in KH) is at most
In the latter case, note that the weights in KH satisfy the triangle inequality, thus the weight of any edge in KH is at most 2(^63^/2+14), and we conclude that Kh has a perfect matching of weight at most (5 + 2)(^/63n/2 + 14) = Y^3087n/2 + 98. By Theorem 1, b(H) = O(^n).	□
CO
m
CD
References
The multiplicative constant ^/3087/2 « 39.29 is likely to be far from the best possible. Indeed, it can be somewhat improved by a more complicated analysis of our argument (e.g., observing that not all 5-faces can appear in T on the lowest possible level, indicating that some of the edges of KH are much shorter than we estimated). Nevertheless, we could not improve it enough to approach the best known lower bound of -y/12/5 ~ 1.549 of Doslic and Vukicevic [2].
[1]	T. Doslic, Bipartivity of fullerene graphs and fullerene stability, Chemical Physics Letters 412 (2005), 336-340.
CO
[2]	T. Doslic, D. Vukicevic, Computing the bipartite edge frustration of fullerene graphs, Discrete Applied Mathematics 155 (2007), 1294-1301.
[3]	M. S. Dresselhaus, G. Dresselhaus, P. C. Eklund, Science of Fullerenes and Carbon Nanotubes, Academic Press, New York (1996).
[4]	S. Fajtlowicz, C. E. Larson, Graph-theoretic independence as a predictor of fullerene stability, Chemical Physics Letters 377 (2003), 485-490.
[5]	P. W. Fowler, D. E. Manolopoulos, An Atlas of Fullerenes, Oxford Univ. Press, Oxford (1995).
CD
[6] I. Gutman, S. J. Cyvin, Introduction to the Theory of Benzenoid Hydro carbons, Springer-Verlag, Berlin (1989).
fi
CD

[7]	F. Kardos, D. Kral', J. Miskuf, J.-S. Sereni, Fullerene graphs have exponentially many perfect matchings, Journal Mathematical Chemistry 46 (2009), 443-447.
[8]	F. Kardos, R. Skrekovski, Cyclic edge-cuts in fullerene graphs, Journal Mathematical Chemistry 22 (2008), 121-132.
r
lO lO
[9] W. Kratschmer, L. D. Lamb, K. Fostiropoulos, D. R. Huffman, Solid C60: a new form of carbon, Nature 347 (1990) 354-358.
o
[10] H. W. Kroto, J. R. Heath, S. C. O'Brien, R. F. Curl, R. E. Smalley, Ceo Buckminsterfullerene, Nature 318 (1985) 162-163.
[11]	J. Malkevitch, Geometrical and Combinatorial Questions About Fullerenes, in: P. Hansen, P. Fowler, M. Zheng (Eds.), Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 51 (2000) 261-266.
o
[12]	R. Taylor, J. P. Hare, A. K. Abdul-Sada, H. W. Kroto, Isolation, separation and characterisation of the fullerences C60 and C70: the third form of carbon, Journal of the Chemical Society, Chemical Communications (1990) 1423-1425.
CO CD
fi
CD CO
fi a
CD