Funne - Le ragazze che sognavano il mare (2016) | Don't Worry, He Won't Get Far on Foot | Базовый курс японского языка

Deeply asymmetric planar graphs

Deeply asymmetric planar graphs

Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78 www.elsevier.com/locate/jctb Deeply asymmetric planar graphs V.A. Aksionova,1 , O.V. Boro...

208KB Sizes 0 Downloads 5 Views

Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78 www.elsevier.com/locate/jctb

Deeply asymmetric planar graphs V.A. Aksionova,1 , O.V. Borodina,2,3 , L.S. Mel’nikova,3,4 , G. Sabidussib,5 , M. Stiebitzc,3 , B. Toftd,3 a Novosibirsk State University, Novosibirsk 630090, Russia b Université de Montréal, Montréal, Canada H3C 3J7 c Ilmenau Technical University, D-98684 Ilmenau, Germany d University of Southern Denmark, DK-5230 Odense M, Denmark

Received 13 June 2001 Available online 17 May 2005

Abstract It is proved that by deleting at most 5 edges every planar (simple) graph of order at least 2 can be reduced to a graph having a non-trivial automorphism. Moreover, the bound of 5 edges cannot be lowered to 4. © 2005 Elsevier Inc. All rights reserved. Keywords: Planar graphs; Asymmetry; Discharging

1. Introduction A graph G is called asymmetric if it admits no non-trivial automorphism. Asymmetry is the typical behaviour of finite graphs. In 1963, Erdös and Rényi [2] proved that almost all E-mail address: [email protected] (B. Toft). 1 The work of this author was supported by Grant 97-01-01075 from the Russian Foundation of Fundamental

Research. 2 The work of this author was supported by the program “Universities of Russia—Fundamental Research” (Project Code 1792). 3 The work of these authors was supported by a Grant from INTAS (Project Code 97-1001). 4 The work of this author was supported by Grant 99-01-00581 from the Russian Foundation of Fundamental Research. 5 The work of this author was supported by Grant OPG-7315 from the Natural Sciences and Engineering Research Council of Canada. 0095-8956/$ - see front matter © 2005 Elsevier Inc. All rights reserved. doi:10.1016/j.jctb.2005.03.002

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

69

graphs are asymmetric. They further proved in [2] that if s(n) is the maximum of the least number of edges which must be added to and/or deleted from, a graph with n vertices in order to produce a graph having a non-trivial automorphism, then s(n)  (n − 1)/2 and limn→∞ s(n)/n = 21 . The aim of this paper is to prove the following result. Theorem 1. Every planar graph with at least two vertices contains a set A of at most five edges whose deletion produces a graph having a non-trivial automorphism. More precisely, A can be so chosen that the edge-deleted graph H := G − A has a pair of vertices x, y such that the transposition (xy) is an automorphism of H . All graphs considered in this paper are finite, undirected and simple. Let G be a plane graph. An edge e of G is called weak if e is incident with two triangular faces, and it is called semiweak if e is incident with only one triangular face. The weight of an edge is the degree sum of its end vertices. Kotzig [3] proved that every 3-connected plane graph has an edge of weight at most 13 and this bound is best possible. Borodin [1] proved that every plane graph has either a weak edge of weight at most 13, or a semiweak edge of weight at most 10, or an edge of weight at most 8, and all three bounds are best possible. The proof of Theorem 1 is based on the following similar result. Theorem 2. Every connected plane graph with at least two vertices has two vertices with degree sum at most 5, or two vertices at distance one or two and with degree sum at most 7, or a weak edge of weight at most 11, or a semiweak edge of weight at most 9. The proof of Theorem 2 is given in Section 2. First, let us show how Theorem 1 follows from Theorem 2. Proof of Theorem 1. Let G be a planar graph with at least two vertices. If G has two isolated vertices, then the theorem is obviously true. Otherwise, G has a component with at least two vertices. From Theorem 2 it then follows immediately in each of the four cases, that there is a set A of at most five edges such that the graph H obtained from G by deleting all edges from A has a pair P of two vertices with identical neighbourhoods outside P. Consequently, the automorphism group of H contains a transposition.  In Section 3 we show that Theorem 1 is not true if five is replaced by four. Theorem 3. There are infinitely many planar asymmetric graphs that remain asymmetric when any set of at most four edges is deleted. 2. Proof of Theorem 2 The proof of Theorem 2 is based on a discharging argument. Throughout this section, let G denote a possible counterexample, that is, a graph satisfying the following properties. (a) G is a connected plane graph with vertex set V, edge set E and face set F, where |V |  2.

70

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

(b) Every weak edge of G has weight at least 12 and every semiweak edge of G has weight at least 10. (c) If x, y ∈ V , x = y, then the degree sum of x and y is at least 8 if the distance of x and y in G is at most two and at least 6 otherwise. For x ∈ V , let d(x) denote the degree of x in G and, for f ∈ F , let s(f ) denote the codegree of f in G. As usual, the codegree of a face f is the length k of the walk (v1 , . . . , vk , v1 ) that bounds f, and we briefly write f = (v1 , . . . , vk ). A vertex of degree k is called a k-vertex and a face of codegree k is called a k-face. The following three statements are immediate consequences of (a) and (c). (d) G has at least three vertices, but no isolated vertices and at most one vertex of degree 1 or 2. (e) If f ∈ F is a k-face, then k  3 and, for k = 3, 4, f is bounded by a cycle. (f) If f ∈ F is a 4-face that is incident with a 3-vertex, then the other three vertices of f have all degree at least 5. Now, we define an initial charge  of G by  d(x) − 6 if x ∈ V , (x) = 2s(x) − 6 if x ∈ F. Then it follows by Euler’s formula that  (x) = 2|E| − 6|V | + 4|E| − 6|F | = −12. x∈V ∪F

Next, we define a new charge ∗ by modifying  according to the rules (R1) and (R2). (R1) Let f = (v1 , . . . , vk ) ∈ F be a k-face with k  4. If k  5 or [k = 4 and f is not incident with a 3-vertex], then we transfer from f to each vi a charge of 1 if d(vi ) = 3 and a charge of 21 otherwise. If k = 4 and f is incident with a 3-vertex, then, by (f), exactly one vertex, say v1 , has degree 3 and we transfer from f to each vi a charge of 1 if i = 1, a charge 3 of 25 if i = 3 and a charge of 10 if i = 2, 4. A 5-vertex v ∈ V is called hungry if the sum of all charges that the faces incident with v transfer to v according to the rule (R1) is smaller than 1. (R2) Let e = uv ∈ E be an edge with d(u)  6. If e is a weak edge, then we transfer from u to v a charge of 1 if v is a 3-vertex, a charge of 21 if v is a 4-vertex and a charge of 1 5 if v is a hungry 5-vertex. If e is a semiweak edge, then we transfer from u to v a charge of 21 if v is a 3-vertex and a charge of 41 if v is a 4-vertex. For each x ∈ V ∪ F , we consider the new charge ∗ (x) which is obtained according to the discharging rules (R1) and (R2). Since our discharging rules only move charge around, and do not affect the total sum, we have   ∗ (x) = (x) = −12 (1) x∈V ∪F

x∈V ∪F

and our aim is to prove the following statement. (g) If x ∈ V ∪ F is a vertex with d(x)  3 or a face, then ∗ (x)  0.

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

71

By (d), there is at most one vertex of degree 1 or 2 and ∗ (x) (x)  − 5 for such a vertex. Consequently, (g) contradicts (1). Therefore, to complete the proof of Theorem 2 it is sufficient to prove (g). Proof of (g). In the first part of the proof, we consider a k-face f ∈ F . Clearly, k  3 and, in the case of k = 3, we have ∗ (f ) = (f ) = 0. Now assume that k  4. Let (f ) denote the sum of all charges that f transfers to the vertices incident with f according to the rule (R1). Then ∗ (f ) = (f )− (f ) and we have to show that (f ) (f ). If k  6, then (f )  k  2k − 6 = (f ). If f is not incident with a 3-vertex, then (f ) = k/2  2k −6 = (f ). Otherwise, 4  k  5 and f is incident with a 3-vertex. In case of k = 4, 3 + 25 = 2 = (f ). In case of k = 5, we infer from we infer from (R1) that (f ) = 1 + 2 · 10 (c), that f is incident with at most one 3-vertex implying that (f )  1 + 4 · 21  4 = (f ). Therefore, ∗ (f )  0 for all f ∈ F . In the second part of the proof, we consider a k-vertex v ∈ V where k  3. Let v1 , . . . , vk denote the neighbours of v in clockwise order and, for i = 1, . . . , k, let fi denote the face incident with the vertices v, vi and vi+1 (all indices are modulo k). Then each face fi transfers a charge to v provided that s(fi )  4. Let  denote the sum of all these charges. To show that ∗ (v)  0, we distinguish two cases. Case 1: 3  k  5. Let  denote the sum of all charges that the vertices v1 , . . . , vk transfer to v according to the rule (R2). Clearly,  as well as  are non-negative and

∗ (v) = (v) +  + . Hence, it suffices to show that  +  − (v) = 6 − k. Let m denote the number of indices i ∈ {1, . . . , k} for which fi is a 3-face. Then s(fi )  4 for all other indices. If fi is a 3-face, then the edge vvi is weak or semiweak and, by (b), d(vi )  10 − k implying d(vi )  6 provided that 3  k  4. If k = 3, then  = 3 − m and, by a simple case analysis based on (R2) (m = 0, 1, 2, 3), it follows that  = m. Thus  +  = 3 = −(v). If k = 4, then, by (f), no 4-face incident with v is incident with a 3-vertex. Consequently,  = (4−m)· 21 . Again, by a simple case analysis based on (R2) (m = 0, 1, 2, 3, 4), it follows that  = m · 21 . Therefore,  +  = 2 = −(v). Now, assume that k = 5. If v is not hungry, then  1 and, therefore,  +  1 = −(v). Otherwise, v is hungry, i.e.  < 1, and we argue as follows. Each face fi with s(fi )  4 3 transfers a charge of s to v where s  10 if vi or vi+1 is a 3-vertex and s  25 otherwise. Note that, by (c), at most one neighbour of v is a 3-vertex. Consequently, m  3, since otherwise 3  2 · 10 + 25 = 1, a contradiction. From (b) it follows that d(vi )  7 if vvi is weak, and d(vi )  5 if vvi is semiweak. Let p denote the number of weak edges incident with v. Then  = p5 . If m = 3, then we distinguish two cases. If all three 3-faces incident with v are consecutive, 3 then p = 2 and  = 25 . Furthermore,  2· 10 and, therefore,  +  1 = −(v). Otherwise, only two of the three 3-faces are consecutive implying that p = 1,  = 15 and, moreover, all neighbours of v have degree at least 5. Hence,  2 · 25 and, therefore,  +  1 = −(v). If m = 4, then p = 3 and  = 35 . Furthermore, all neighbours of v have degree at least 5 and, therefore,  25 . If m = 5, then p = 5 and  = 5 · 15 = 1. Therefore, in both cases, we have  +  1 = −(v). This completes the proof for case 1.

72

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

Case 2: k  6. A neighbour vi of v is called active if v transfers a charge to vi . Clearly by (R2), if vi is active, then vi has degree 3, 4 or 5 and the edge vvi is weak or semiweak. If  denotes the sum of all charges that v transfers to the active vertices, then

∗ (v) = (v) +  − . For q = 3, 4, 5, let aq denote the number of active q-vertices. We distinguish three subcases. First, we consider the case that k = 6. If vi is active, then, by (b), vi is a 4-vertex and vvi is semiweak. Hence there is a face f ∈ {fi−1 , fi } of codegree at least 4. From (b) and (c) we then conclude that s(f )  5 or f is a 4-face that is not incident with any 3-vertex. Consequently, f transfers a charge of 21 to v and v transfers a charge of 41 to vi . This implies immediately that  −  0 and, therefore, ∗ (v) (v) = 0. Next, we consider the case that k = 7. First, we claim that there are no five consecutive active 5-vertices. Suppose this is not true and let v1 , v2 , v3 , v4 , v5 be five such active 5-vertices. Then, by (R2), the vertices v1 , v2 , v3 , v4 , v5 are hungry and the edges vv1 , vv2 , vv3 , vv4 , vv5 are weak. Therefore, f7 , f1 , f2 , f3 , f4 , f5 are 3-faces. Furthermore, each of v2 , v3 , v4 is incident with at least three 3-faces, as proved in Case 1. By (b), the edges v1 v2 , v2 v3 , v3 v4 , v4 v5 are not weak and, thus, all neighbours of v2 , v3 , v4 have degree at least 5. This implies that v3 is incident with exactly three 3-faces and if there is a 4-face f incident with v3 , then f is not incident with any 3-vertex. Consequently, the faces incident with v3 transfer in total a charge of 2 · 21 = 1 to v3 , contradicting the assumption that v3 is hungry. This contradiction proves the claim. Clearly, the claim implies that a5  5. If a5 = 5, then from the above claim and (b) we conclude that all neighbours of v have degree at least five and hence a3 = a4 = 0. Consequently,  a5 · 15  1 and, therefore, ∗ (v) (v) −  = 1 −  0. Otherwise, a5  4 and we argue as follows. Let vi be an active vertex of degree 3 or 4. Then, by (b) and (R2), the edge vvi is not weak but semiweak and, therefore, there is a face f ∈ {fi−1 , fi } of size 3 at least 4. Hence, f transfers a charge of at least 10 to v. If vi is a 4-vertex, then, by (f), no 4-face incident with vi is incident with a 3-vertex and, therefore, f transfers a charge of 21 to vi . The vertex v transfers to vi a charge of 21 if d(vi ) = 3 and a charge of 41 if d(vi ) = 4. Consequently, if a3 = 0, then  −  −a5 · 15  − 45 implying that ∗ (v) = (v)+  −  0. 13 3 If a3  1, then, by (c), a3 = 1 and a4 = 0. Therefore,  21 +a5 · 15  10 and  10 implying ∗ that  (v) = 1 +  −  0. Finally, we consider the case that k  8. If a3  1, then, by (c), a3 = 1 and a4 = 0. Let v1 be the active 3-vertex. If vk or v2 is an active 5-vertex, then (R2) implies that vk v1 or v1 v2 is an edge, a contradiction to (b). Consequently, a5  k − 3 and, therefore,  1 + (k − 3) · 15  k − 6 = (v). If a3 = a4 = 0, then  k · 15  k − 6 = (v). Hence, in both cases, ∗ (v) (v) −  0. Otherwise, a3 = 0 and a4  1 and we argue as follows. Let a denote the number of all active 4-vertices vi for which vvi is weak. If vi is such a vertex, then, by (b), neither vi−1 nor vi+1 is active and we conclude that  a · 21 + (k − 2a) 41 = k4  k − 6 = (v). Hence, ∗ (v) (v) −  0. This completes the proof of statement (g) and, therefore, also of Theorem 2. 

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

73

p

a1

a2

···

a3

a4

···

···

a′1

a′2

a′3

a4′

n Fig. 1.

3. Proof of Theorem 3 The number of five edges in Theorem 1 cannot be lowered. There exist asymmetric planar graphs which are deeply asymmetric in the sense that the deletion of any four or fewer edges always results in an asymmetric graph. In this section we construct an infinite family of such graphs. For technical reasons they are rather large (the smallest has 607 vertices) and they are close to being triangulations. There is a trade-off between the size of these graphs and the possibility of giving a relatively simple proof of their deep asymmetry. The proof is based on the fact that in graphs which are like triangulations in a certain well-defined sense, two automorphisms coincide globally if they do so on some triangle. Let n be some positive integer, and consider the disk-like graph D obtained from the graph shown in Fig. 1 by identifying the vertices ai and ai for i = 1, 2, 3, 4. Clearly, D is planar, and all its faces are triangles with the exception of the face bounded by the n-cycle C resulting from the path at the bottom of Fig. 1 by identification of a4 and a4 . Except for p which is of degree n all vertices of D are of degree 5 or 6. Let d1 , . . . , d5 be integers such that d1  11, and di+1  di + 5,

for i = 1, . . . 4

(2)

and put n = d1 + · · · + d5 − 5.

(3)

Let T be the plane tree which consists of a central vertex c with five neighbours c1 , . . . , c5 , and for each i = 1, . . . , 5 a fan of di − 1 pendant vertices attached to ci (see Fig. 2). Denote the set of these vertices by Fi .

74

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

d1-1

d5-1

c1

d2-1 c2

c5 c c4

c3

d4-1

d3-1 Fig. 2.

The degrees of the non-pendant vertices of T are dT (c) = 5, dT (ci ) = di for i = 1, . . . , 5, and the number of pendant vertices is n. The smallest possible value of n (taking equality everywhere in (2)) is 100. Now form the graph G by taking D (with n given by (3)), and identifying the vertices of the cycle C of D with the pendant vertices of T in the cyclic order given by the embedding of T in the plane. Clearly G is planar; p and c may be thought of as the north and south poles when the graph is embedded in the sphere. All faces of G are triangles except for the five pentagons at the south pole. The vertices of G have the same degree they had in D and T, respectively, with the exception of the vertices of C whose degree is now 6. Note that no two 5-vertices of G are adjacent. Proposition 4. G is deeply asymmetric. To show this take any set A of at most four edges of G, and consider the graph GA obtained from G by deleting all edges belonging to A. For the proof we need two properties of GA , both concerning its automorphisms. First, we prove the following result. Proposition 5. There is no pair P of vertices whose neighbourhoods outside P are identical in GA . This implies, in particular, that no transposition is an automorphism of GA .

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

75

Proof. Suppose on the contrary that there is a pair P = {x, y} of vertices with the same neighbourhood outside P in GA . Let m denote the number of common neighbours of x and y in GA . In G any two vertices have at most two common neighbours. Consequently, either m  1 or m = 2. In the first case, the degree of x and of y is at most 2 in GA , but at least 5 in G, contradicting |A|  4. In the second case, the degree of x and of y is at most 3 in GA . Hence x and y are adjacent and both of degree 5 in G, a contradiction.  Definition 6. Let H be any graph, and let  be a triangle contained in H. A vertex x of H is called accessible from  if there is a sequence of triangles 0 , . . . , r in H such that 0 = , x belongs to r , and i , i+1 have an edge in common for i = 1, . . . , r. The sequence 0 , . . . , r is said to connect x to . Some form of the next proposition is undoubtedly part of the folklore (at least in the planar case) but we are unaware of any references in the literature. Proposition 7. Suppose that H is a graph containing a triangle  and such that no edge of H belongs to more than two triangles. Let  be an automorphism of H which fixes the three vertices of . Then  fixes every vertex of H which is accessible from . Proof. By induction on the length of sequences connecting accessible vertices to . Let  = 0 , 1 , . . . , r be such a sequence for a vertex x, and suppose we have already shown that the vertices of r−1 are fixed by . In particular,  fixes the endpoints of the common edge of r−1 and r , and since r is the only triangle of G sharing this edge with r−1 it follows that  also fixes x.  Proof of Proposition 4. Let  be an arbitrary automorphism of GA and let F be the set of all vertices of GA that are fixed by . For the proof of Proposition 4 we have to show that every vertex of GA belongs to F. In order to avoid undue length, the proof will be sketchy in certain places. From (2) and |A|  4 it follows that in GA the vertices p, c1 , . . . , c5 have different degrees  7, whereas all other vertices of GA have degrees  6. Hence p, c1 , . . . , c5 ∈ F . This in turn implies that c ∈ F . Let D  denote the planar graph obtained from D by deleting the vertex p and let V  denote the vertex set of D  . Clearly, it suffices to show that V  ⊆ F . The 6n vertices of D  are arranged in 2n vertical triplets (see Fig. 3). The vertices of each triplet form a path (x, y, z) of length 2, where we choose the order in such a way that the first vertex x is either on C or a neighbour of p. The set of all triplets has two circular orders in D  (clockwise and counterclockwise). This gives rise to two directed Hamiltonian cycles C1 and C2 of D  , whose orientation is so chosen that both of them traverse each triplet in the order x, y, z described above. From (2) and |A|  4 it follows that in G one can choose three consecutive vertices u, v, w of the cycle C, not all in the same fan Fj , and such that none of their incident edges belongs to A. Without loss of generality we may assume that u, v ∈ Fj and w ∈ Fj +1 . In particular we have that the triangle  = cj uv and the two edges vw and wcj +1 belong to GA (see Fig. 4).

76

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

x z y

y z x

(a) x

z y

y z (b)

x Fig. 3. (a) Bold edges: C1 ; (b) Bold edges: C2 .

v

w

u

cj+1

cj

c Fig. 4.

Now note that v is the only vertex in GA which is adjacent to cj and at distance 2 from cj +1 . Since both cj and cj +1 belongs to F this implies that v∈F ; and since  is the only triangle in GA containing the edge cj v it follows that u∈F . Thus  fixes every vertex of .

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

77

Consider the five consecutive triplets in D  , the first of which starts at u and the last of which starts at w. Let W denote the vertex set of these five triplets. By the same argument as above, we can choose the vertices u, v and w such that also no edge incident with a vertex in W belongs to A. Then every vertex of W is accessible from  in GA and, by Proposition 7, it follows that  fixes every vertex of W , i.e. W ⊆ F . For the rest of the proof, suppose that U = V  − F is non-empty. From W we then traverse the two Hamiltonian cycles C1 and C2 according to their orientations. For i = 1, 2, let xi be the first vertex of U we meet on Ci , and let Pi be the vertices we meet before xi traversing Ci . Moreover, let Qi = Pi ∪ {p, c1 , c2 , c3 , c4 , c5 }. Then W ⊆ Pi ⊆ Qi and Qi ⊆ F , i.e.  fixes every vertex of Qi . The distinct vertices xi and (xi ) belong both to U and have in GA the same neighbours in F and hence in Qi . In G the vertex xi has exactly three neighbours in Qi , but no two distinct vertices of V  − P1 − P2 , and hence of U, have more than one common neighbour in Qi . Consequently, if Si is the set of vertices of Qi that are neighbours of xi in G, but not in GA , then |Si |  2 for i = 1, 2. This means that A must contain two edges joining x1 to Q1 and similarly two edges joining x2 to Q2 . Now we distinguish two cases. First, we consider the case that x1 = x2 . Then this vertex belongs to a triplet (x, y, z) of D  and U ⊆ {x, y, z}. Since by Proposition 5 the automorphism  is not a transposition, this implies that U = {x, y, z}, x = x1 = x2 , and the three vertices of U form a cycle of . Therefore, the vertices of U have the same degree d in GA . Since |Si |  2 and x has degree 6 in G, we obtain d  4. But in G the vertex y has degree 6 and the vertex z has degree 5, contradicting |A|  4. Next, we consider the case x1 = x2 . Then x1 and x2 belong to different triplets of D  . Since |A|  4 and |Si |  2 for i = 1, 2, this implies that |S1 | = |S2 | = 2 and |A| = 4, where A contains two edges joining x1 to Q1 and two edges joining x2 to Q2 . Then the vertices x1 and x2 have degree  4 in GA whereas all other vertices of U have degree  5 in GA . Consequently, (x1 ) = x2 and (x2 ) = x1 and, therefore, x1 and x2 have the same degree in GA as well as in G. Furthermore, it follows that x1 and x2 have in GA the same neighbours in F. In GA the vertex xi (i = 1, 2) has exactly one neighbour qi ∈ Qi . Since Qi ⊆ F , this implies that qi is a common neighbour of x1 and x2 in GA . If q1 or q2 belongs to {p, c1 , c2 , c3 , c4 , c5 }, then the vertices x1 and x2 are either both on C or both neighbours of p, and, therefore, there are two triplets in D  of the form (x1 , y1 , z1 ) and (x2 , y2 , z2 ). But then in GA the vertex yi has two neighbours in Pi ⊆ F and, since there is no other such vertex in U, we conclude that yi ∈ F for i = 1, 2. Since y1 ∈ F is a neighbour of x1 in GA it is also a neighbour of x2 = (x1 ), a contradiction. If neither q1 nor q2 belongs to {p, c1 , c2 , c3 , c4 , c5 }, then qi ∈ Pi for i = 1, 2, and, therefore, q1 = q2 . Hence, x1 and x2 are two vertices of the same degree in G that belong to different triplets of D  and have exactly two common neighbours one of which belongs to P1 and the other one belongs to P2 . This implies by a simple case analysis that x1 and x2 are vertices of degree 5 in G that belong to two consecutive triplets of D  . But then U = {x1 , x2 } and, therefore,  is a transposition, contradicting Proposition 5. Therefore, in both cases we arrive at a contradiction. This proves Proposition 4 and hence Theorem 3. 

78

V.A. Aksionov et al. / Journal of Combinatorial Theory, Series B 95 (2005) 68 – 78

It is very easy to find sets A of five edges where GA is symmetric. Just take an edge xy of weight 11 and delete the edges incident to x or y but not on the same faces as xy. All vertices other than x and y are fixed by every automorphism of GA . This is the only way to get a non-trivial automorphism in GA when |A|  5. Theorem 1 can easily be extended to an arbitrary surface, i.e. a connected compact 2dimensional manifold. To see this, consider a graph G with vertex set V and edge set E that is embedded on a given surface  of Euler characteristic ε = ε(). Then Euler’s formula tells us that |V | − |E| + |F |  ε, where F is the set of faces. Therefore, if |V |  3, then |E|  3|V | − 3ε. For ε  1, this implies that G has a vertex of degree at most H (ε) − 1, where   √ 7 + 49 − 24ε H (ε) = 2 is the Heawood number of . Consequently, G has two non-adjacent vertices with degree sum at most 2H (ε) − 2 or two adjacent vertices with degree sum at most 2H (ε) − 1. This implies that there is a set A of at most 2H (ε)−2 edges such that the graph GA obtained from G by deleting all edges from A has a pair P of two vertices with identical neighbourhoods outside P. Then, clearly, GA has a non-trivial automorphism. However, except for the plane, we do not know the sharpest possible bound. References [1] O.V. Borodin, Joint extension of two theorems of Kotzig on 3-polytopes, Combinatorica 13 (1993) 121–125. [2] P. Erdös, A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 295–315. [3] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Casopis. 5 (1955) 101–113.