ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 10 (2016) 323-332 The number of edges of the edge polytope of a finite simple graph Takayuki Hibi Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan Aki Mori Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan Hidefumi Ohsugi Department ofMathematical Sciences, School ofScience and Technology, Kwansei Gakuin University, Sanda, Hyogo, 669-1337, Japan Akihiro Shikama Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan Received 6 September 2014, accepted 8 October 2015, published online 5 February 2016 Let d > 3 be an integer. It is known that the number of edges of the edge polytope of the complete graph with d vertices is d(d - 1)(d - 2)/2. In this paper, we study the maximum possible number ^d of edges of the edge polytope arising from finite simple graphs with d vertices. We show that = d(d - 1)(d - 2)/2 if and only if 3 < d < 14. In addition, we study the asymptotic behavior of Tran-Ziegler gave a lower bound for ^d by constructing a random graph. We succeeded in improving this bound by constructing both a non-random graph and a random graph whose complement is bipartite. Keywords: Finite simple graph, edge polytope. Math. Subj. Class.: 52B05, 05C30 E-mail addresses: hibi@math.sci.osaka-u.ac.jp (Takayuki Hibi), a-mori@cr.math.sci.osaka-u.ac.jp (Aki Mori), ohsugi@kwansei.ac.jp (Hidefumi Ohsugi), a-shikama@cr.math.sci.osaka-u.ac.jp (Akihiro Shikama) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 324 Ars Math. Contemp. 10 (2016) 255-268 1 Introduction The number of ¿-dimensional faces of a convex polytope has been studied by many researchers for a long time. One of the most famous classical results is "Euler's formula." The extremal problem concerning the number of faces is an important topic in the study of convex polytopes. On the other hand, the study of edge polytopes of finite graphs has been conducted by many authors from viewpoints of commutative algebra on toric ideals and combinatorics of convex polytopes. We refer the reader to [2, 3] for foundations of edge polytopes. Faces of edge polytopes are studied in, e.g., [2,4, 5]. Recently, Tran and Ziegler [6] studied this extremal problem on edge polytopes. In particular, using [5, Lemma 1.4], they gave bounds for the maximum possible number ^d of edges of the edge polytope arising from finite simple graphs with d vertices. Following [1, Question 1.3], we wish to find a finite simple graph G with d vertices such that the edge polytope of G has edges and to compute Recall that a finite simple graph is a finite graph with no loops and no multiple edges. Let [d] = {1,..., d} be the vertex set and Qd the set of finite simple graphs on [d], where d > 3. Let ej denote the ith unit coordinate vector of the Euclidean space Rd. Let G G Qd and E(G) the set of edges of G. If e = {i, j} G E(G), then we set p(e) = ej + ej G Rd. The edge polytope PG of G G Qd is the convex hull of the finite set {p(e) : e G E(G)} in Rd. Let e(G) denote the number of edges, namely 1-dimensional faces, of PG. For example, consider the case of the complete graph Kd on [d]. By [5, Lemma 1.4], for edges e and f (e = f) of Kd, the convex hull of {p(e), p(f)} is an edge of the edge polytope PKd if and only if e and f have a common vertex. Hence, e (Kd) = d(d-1) = d(d - 1)(d-2)/2. On the other hand, e(Km,n) = mn(m + n - 2)/2, where Km,n is the complete bipartite graph on the vertex set [ m ] U {m + 1,..., m + n} for which m, n > 1 (see [4, Theorem 2.5]). In this paper, we are interested in = max{ e(G) : G G Qd } for d > 3. Theorem 1.1. For an integer d > 3, let Qd be the set of finite simple graphs on [d]. Given a graph G G Qd, let e(G) denote the number of edges of the edge polytope PG of G. Then, the following holds: (a) If 3 < d < 13 and G G Qd with G = Kd, then e(G) < e(Kd). (b) Let G G Q 14 with G = K14. Then e(G) < e(Ki4). Moreover, e(G) = e(Ki4) if and only if either G = K14 — K4,5 or G = K14 — K5,5. (c) If d > 15, then there exists G G Qd such that e(G) > e(Kd). We devote Section 2 to giving a proof of Theorem 1.1. At present, for d > 15, it remains unsolved to find G G Qd with = e(G) and to compute (Later, we will see that ^15 > e(K15) + 50 = 1415.) In Section 3, we study the asymptotic behavior of Recently, Tran-Ziegler [6] gave a lower bound for by a random graph: 118 1 e(G(d, 1^V3)) = — d4 + — d3--d2 + - d. ( ( , ' )) 54 + 18 27 +3 They also gave an upper bound for < (32 + o(1))d4. (However, this upper bound is not sharp. See [6, Remark].) In this paper, we succeeded in improving their lower bound by constructing a non-random graph (see Example 3.1) and a random graph whose complement is bipartite (see Theorem 3.2): 5V5 — 11 ,4 12V5 — 27 o 19V5 — 44 ,2 , e(G) = -i—--d4---d3 +---d2 + d, T. Hibi et al.: The number of edges of the edge polytope of a finite simple graph 325 where G = Kd - G(Kd/2jd/2,p) with p = 3 - %/5. These results suggest the following: Conjecture 1.2. Let G G Qd with ^d = e(G). Then, the complement of G is a bipartite graph. Note that, by Theorem 1.1, this conjecture is true for 3 < d < 14. 2 Proof of Theorem 1.1 In this section, we give a proof of Theorem 1.1. The following lemma is studied in [5, Lemma 1.4]. Lemma 2.1. Let e and f (e = f) be edges of a graph G G Qd. Then, the convex hull of {p(e),p(f)} is an edge of the edge polytope if and only if one of the following conditions is satisfied. (i) e and f have a common vertex in [d\. (ii) e = {i, j} and f = {k, l} have no common vertices, and the induced subgraph of G on the vertex set {i, j, k, l} has no cycles of length 4. The complement graph G of a graph G G Qd is the graph whose vertex set is [d] and whose edges are the non-edges of G. For a vertex i of a graph G, let degG(i) denote the degree of i in G. We translate Lemma 2.1 in terms of the complement G of G. Lemma 2.2. Let H be the complement of a graph G G Qd. Then, we have d 'd - 1 - degH(i) e(G) = £ (d - 1 -2degH(i))+ a(H)+ b(H) + c(H) 2 i=1 x 1d = (d) = e(Kd+1 — H) — e(Kd+1) — e(Kd — H ) + e(Kd) = t fd — degH2 (i)) — t fd — 1 — degHi + V(H) i=1 ^ 2 ' i=1 ^ 2 / + d(d — 1)(d — 2) (d +1)d(d — 1) 22 ^ + ^ ^ — degHi (i)^ — — 1 — degHi (i)^ ^ + ^(H) — 3d(d — 1) (d) + it (d — 1 — degHi (i)) + ^(H ) — ^^^ ^ ' i=1 d V>(H) — ^ degHi (i) i=1 = V(H ) — 2|E(H)|, as desired. □ Proposition 2.4. Let G e Qd and let H1, H2,..., Hm be all the nonempty connected components of G. Then, e(Kd) — e(G) = 5^j=1(e(Kd) — e(Kd — Hj)). Proof. Let H = G and let Hj = Kd — Hj for 1 < j < m. Then, it is easy to see that |E(H)| = j |E(Hj)|, £?=! degH(i) = E^ EU degH. (i), «(H) = E™! a(Hj), b(H) = j b(Hj), and c(H) = E^ c(Hj). Thus, by Lemma 2.2, we are done. □ A graph G G is called bipartite if [d] admits a partition into two sets of vertices V and V2 such that, for every edge {i, j} of G, either i G V1, j G V2 or j G V1, i G V2 is satisfied. A complete bipartite graph is a bipartite graph such that every pair of vertices i, j with i g V1 and j G V2 is adjacent. Let Km,n denote the complete bipartite graph with |V1| = m and |V2| = n. Proposition 2.5. Let G = Kd — Km,n such that m + n < d and m, n > 1. Then, e(G) — e(Kd) = ^ mn(m + n — 6)d — ^ mn(3mn + 2m2 + 2n2 — 5m — 5n — 13). T. Hibi et al.: The number of edges of the edge polytope of a finite simple graph 327 Proof. Let H = Km,n. Then, (n \ (1 -0(H) — 2|E(H )| = mi j + \ 2 J — 2mn = 2 mn(m + n — 6)' Moreover, since Km+n — Km,n is the disjoint union of Km and Kn, we have m(m — 1)(m — 2) n(n — 1)(n — 2) /m\ /n ^(m + n) = -2-+-2-+V2M2 (m + n)(m + n — 1)(m + n — 2) = - mn(mn — 7m — 7n + 13) 4 by Lemma 2.1. Hence, by Proposition 2.3, e(G) — e(Kd) = — mn(m + n — 6)(d — (m + n)) + — mn(mn — 7m — 7n + 13) = — mn(m + n — 6)d — — mn(3mn + 2m2 + 2n2 — 5m — 5n — 13), as desired. □ Let k3(H) denote the number of triangles (i.e., cycles of length 3) of H. The following lemma is important. Lemma 2.6. Let H be the complement graph of G G Qd. Then, we have d2 — 16d + 29 3 e(G) < e(Kd) +-|E(H )| — -(d — 8)k3(H ). Proof. The number of pairs of edges satisfying Lemma 2.1 (i) is, by Lemma 2.2, e(Kd) — (2d — 3) |E(H)| + 1 £ti degH(i) For an edge {i, j} of H, let k3(i, j) be the number of triangles in H containing {i, j}. We define three subsets of [d] \ {i, j}: = {* G [d] \{i,j} Yij = G [d] \{i,j} Zi,j = {* G [d] \{i,j} {i,^}G E(H), {j,i}GE(H)}, {j, G E(H), {i, G E(H)}, {i, G E(H), {j, G E(H)}. It then follows that, |Xijj | + |Yi,j | + |Zijj | + ^ (i, j) = d — 2, and 1 d 1 2EdegH(i) = 2 ^ (degH (i)+degH(j)) i=1 {i,j}eE(H) = 1 E (|Xi,j | + |Yi,j | + 2k3(i,j) + 2) {i,j}eE(H) = |E(H )| + 3k3(H ) + 2 E (|Xi,j | + |Yi, {i,j}£E(H) 328 Ars Math. Contemp. 10 (2016) 255-268 Second, we count the number of pairs satisfying Lemma 2.1 (ii). By Lemma 2.2, this number is equal to a(H) + b(H) + c(H). Here, we count the number of the induced subgraphs H' of type (a), (b) and (c) containing an edge e = {i, j} of H. If e is an edge of H', then the other two vertices i and m of H' satisfy exactly one of the following conditions: (i) i € Xj, m € ; (ii) i € , m € Zj,j; (iii) i € Zj,j, m € Xj,j. If i, j, i, m satisfy condition (i), then one of the following holds: • H' is a path (ei, e2, e3) and e = e2 (type (a)); • H' is a cycle of length 4 and e is one of four edges (type (b)). It then follows that a(H )+4b(H )= £ |Xj,j ||Yj,j |. If i, j, i, m satisfy either condition (ii) or (iii), then one of the following holds: • H' is a path (e1, e2, e3) and e € {e1, e3} (type (a)); • H' is a path (e1, e2) with one isolated vertex and e € {e1, e2} (type (c)). It then follows that 2a(H)+2c(H)= £ (|Yj,j||Zj,j1 + |Zj,j||Xj,j|). {i,j}£E(H) Thus, we have a(H) + b(H) + c(H ) = - + £ (1 |Xj,j | + 1 ||Zj,j | + 2 |Zj,j ||Xj,j |). {i,j}£E(H) Subject to |Xj,j | + | + |Zj,j | = d - 2 - k3(i, j), we study an upper bound of a = £ [|Xj,j | + |Yj,j | + 1 |Xj,j ||Yj,j | + 2 |Yj ||Zj,j | + 2 |Zj,j ||Xj,j A . Each summand of a satisfies |Xj,j | + |Yj,j | + 1 |Xj,j ||Y,j | + 1 |Y ,j ||Zj,j | + 2 |Zj,j ||Xj,j | = 1 |Xi,j||Y,j| + 2(|Xi,j| + |Y,j|)(d - 1 - k3(i, j) - (|Xj,j| + |Y,j|)) < 1 (|Xj,j| + |Yj,j^2 + 2(|Xj,j| + |Y,j|)(d - 1 - k3(i, j) - (|Xj,j | + |Yj,j |)) = - 16(|Xj ,j | + |Y ,j |)2 + d -1 -2k3(i,j)(|Xj ,j | + |Y ,j |). T. Hibi et al.: The number of edges of the edge polytope of a finite simple graph 329 The last function has the maximum number 7(d - 1 - k3(i, j))2 when |Xjj | + | = 7(d - 1 - k3(i, j)). Hence, E 1(d - 1 - k3(i,j))2 < E 7(d - 1)(d - 1 - k3(i,j)) {ij}eE(H) {ij}eE(H) = 1 E (d - 1)2 - 1 E (d - 1)k3(i,j) {i,j}eE(H) {i,j}eE(H) 1 3 = 7(d - 1)2|E(H)|- 7(d - 1)ks(H) is an upper bound of a. Thus, 1 3 e(Kd) - (2d - 3)|E(H)| + |E(H)| + 3k3(H) + ^(d - 1)2|E(H)| - -(d - 1)k3(H) is an upper bound of e(G) as desired. □ Using Proposition 2.5 and Lemma 2.6, we prove Theorem 1.1. Proof of Theorem 1.1. (a) Let 3 < d < 13 and G G Q.d with G = Kd. If d = 3, then e(G) < e(Kd) is trivial. If d =4, then e(K4) = 12. Since |E(G)| < 6, we have e(g) < (2) =10 < e(K4). Let d > 5 and let H be the complement graph of G. By Lemma 2.6, d2 — 16d + 29 3 e(G) - e(Kd) < d ^ + 29 |E(H)| - 7(d - 8)^(H). If 8 < d < 13, then e(G) - e(Kd) < 0 since d2-16d+29 < 0, |E(H)| > 0 and k3(H) > 0. Let 5 < d < 7. Then, - f |E(H )| + fk3(H) if d =5, e(G) - e(Kd) <{ -31 |E(H)| + 6k3(H) if d =6, - f |E(H )| + 3 k3(H) if d =7. Hence, if k3(H) < 2, then e(G) - e(Kd) is negative. On the other hand, if k3(H) > 3, then |E(H)| > 5. Since ^(H) < (d), it follows that e(G) - e(Kd) is negative. (b) Let G g 014 with G = K14 and let H = G. We need to evaluate the function which appears in the proof of Lemma 2.6 more accurately by focusing on d = 14. Let |Zi,j| = 12 - k3(i, j) - |Xi,j| - |Yi,j| and f = |Xi'j | + |Yi'j | +4 |Xi,j ||Yi,j | + 2 |Yi,j ||Zi,j | + 2 |Zi,j ||Xi,j | g = - ¿(Xi'j | + |Yi'j |)2 +13 k3(i,j)(Xi'j | + |Y'j |) be functions of |Xi'j| and |Yi'j|. Recall that f < g < 7 (13 - k3(i, j))2 and g = 7(13 -k3(i,j))2 when |xi'j| + |Yi'j| = 4(13 - j)). If 1 < k3(i,j) < 12, then 1 13 11 1 13 7(13-k3(i, j))2 = 24-13k3(i, j)- 17- + 7(k3(i, j)-1)(k3(i, j)-12) < 24-13^(i, j). 330 Ars Math. Contemp. 10 (2016) 255-268 If j) = 0, then 7(13 - j))2 = 24 + 1/7. However, since 4 (|Xi'j 1 + |Yj 1 + 1 |Xi,j||Yj| + 1 ||Zi,j| + 2||Xi,j|) is an integer, the value of f is at most 24 if |Xjj | and || are non-negative integers. Thus, for k3(i, j) = 0,1,..., 12, the value of f is at most 24 - 13k3(i, j) if |Xj j| and | Yj | are non-negative integers. Thus, by the same argument in the proof of Lemma 2.6, e(G) - e(K14) is at most -24|E(H)| + 3k3(H) + 24|E(H)| - ^) - = -yMH) - ^ < 0. Therefore, e(G) < e(K14). Suppose that e(G) = e(KM). Then, -f kj(H) - > 0. Since fc^H), a(H) > 0, we have k3(H) = a(H) = 0. Moreover, |Xi'j | + |Yi'j | + 4 |Xi'j ||Yi'j | + 2 |Yi'j ||Zi'j | + 1 |Zi'j ||Xi'j | = 24 and |Xj j| + |Yj | + |Zj j| = 12 for an arbitrary edge {i, j} of H. It is easy to see that |Xi'j | + |Yi'j | g'{7, 8}. It then follows that, for an arbitrary {i,j} G E(H), (X^-1, |Yj |, |Zi'j |) G {(3,4,5), (4, 3,5), (4,4,4)}. In particular, the degree of each vertex is either 0, 4 or 5. Moreover, since k3(H) = 0, {j} U Xjj and {i} U Yj are independent sets. Hence, by a(H) = 0, the induced subgraph of H on {i, j} U Xjj U Yj is the complete bipartite graph K|Xi,j1 + 1'^- |+i. Suppose that an edge {i, j} of H satisfies (|Xjj1, |Yi'j |, |Zijj |) = (4,4,4). Then, the induced subgraph of H on {i, j} U Xjj U Yj is K5'5. Since the degree of any vertex of H is either, 0, 4 or 5, other four vertices are isolated. Therefore, G = K14 - K5'5. It is enough to consider the case that (|XS't|, |YS't|, |ZS't|) = (4,4,4) holds for every edge {s,t}. Suppose that (|Xj j|, |Yj|) = (3,4). Then, the induced subgraph of H on {i, j} U Xi'j U Yj is K4'5. Since (|XM|, |YM|, |ZM|) = (4,4,4) for each edge {s,t}, the degree of every vertex in {i} U Yj is 4. In this case, K4'5 is a connected component of H. Since the degree of other five vertices is at most 4, it follows that they are isolated vertices. Therefore, G = K14 - K4'5. (c) Let d > 15 and let G = - K^« G By Proposition 2.5, we have e(G) - e(Kd) = ^mn(m + n - 6)d - ^mn(3mn + 2m2 + 2n2 - 5m - 5n - 13). When m = n = 5, we obtain e(G) - e(Kd) = 50(d - 14) > 0 as desired. □ 3 Asymptotic behavior of For 0 < p < 1 and an integer d > 0, let G(d,p) denote the random graph on the vertex set [d] in which the edges are chosen independently with probability p. For a graph H on the vertex set [d] and 0 < p < 1, let G(H,p) denote the random graph on the vertex set [d] in which the edges of H are chosen independently with probability p and the edges not belonging to H are not chosen. Tran-Ziegler [6] showed that, for the random graph G(d, 1/^3), 118 1 e(G(d, 1/V3)) = -d4 + -d3 - -d2 + ^d, T. Hibi et al.: The number of edges of the edge polytope of a finite simple graph 331 and hence this is a lower bound for First, for d > 0, we give an example of a (non-random) graph G on the vertex set [d] such that e(G) > e(G(d, 1/V3)). Example 3.1. Let G = Kd - Kad,ad - K(1/2-a)d,(i/2-a)d where a = ^ (7 + V2T) and d > 0. By Propositions 2.4 and 2.5, it follows that £(G) = i48d4 + Td3 - TT2d2 + d. Since 1/54 = 0.0185 and 9/448 = 0.0201, we have e(G) > e(G(d, 1/V3)) for d > 0. Second, we give a random graph G on the vertex set [d] such that e(G) >e(G(d, 1/V3)) for d > 0. Theorem 3.2. For an integer d, let G be a random graph Kd — G(Kd/2d/2,p) with p = 3 — a/5. Then, £(G)=^ - 11 d4 - ^ - 27 d3 + ^ - 44 d2 + d. v y 8 2 2 In particular, we have e (G) > e(G(d, 1/>/3)) for all d > 0. Proof. Let m = d/2 and let [d] = V U V2 be a partition of the vertex set of Km,m. The number of pairs of edges {i, j}, {i, k} satisfying Lemma 2.1 (i) is ni = m(m - 1)(m - 2) + 2m2(m - 1)(1 - p) + m2(m - 1)(1 - p)2 where each term corresponds to the case when (i) i, j, k G Vs, (ii) i, j G Vs, k G Vs and (iii) i G Vs, j, k G Vs, respectively. Next, we study the number of pairs of edges {i, j}, {k,^} satisfying Lemma 2.1 (ii). Let Gijk£ denote the induced subgraph of G on the vertex set {i, j, k, c [d]. If either "i,j,M G Vs" or "i, ^ G Vs and j, k G Vs" holds, then {i, j, k, is a cycle of Gijk£ whenever {i, j}, {k, g E(G). Hence, we consider the following two cases: Case 1. Suppose i, j G Vs and k, I G Vs. Then, Gijk£ has a cycle of length 4 if and only if either {i,k}, {j,^} G E(G) or {i,^}, {j,k} G E(G) holds. Thus, the expected number of pairs of edges is n2 = (m )2(1 - (1 - p)2)2. Case 2. Suppose that i G Vs and j, M G V hold. Then, all of {k, ¿}, {j, k} and {j, are edges of G. On the other hand, {i, j} is an edge of G with probability 1 - p. If {i, j} is an edge of G, then Gijke has a cycle of length 4 if and only if either {i, k} G E(G) or {i, G E(G) holds. Thus, the expected number of pairs of edges is ^3 = m2(m - 1)(m - 2)(1 -p)p2. Therefore, e(G) = + n2 + n3. If m = d/2 andp = 3 - a/5, then e(G)=5^ - 11 d4 - 12^ - 27d3 + 19^ - 44 d2 + d, whose leading coefficient is 5V58-ii = 0.0225425. □ 332 Ars Math. Contemp. 10 (2016) 255-268 Remark 3.3. By Theorem 3.2, the graph G in Example 3.1 does not satisfy = e(G) for d > 0. In fact, for d = 20, by Propositions 2.4 and 2.5, it follows that Let G' G n2o be the graph such that G' is the bipartite graph with E(G') = {{1,12}, {1,14}, {1,15}, {1,16}, {1,18}, {1,19}, {1, 20}, {2,11}, {2,12}, {2,13}, {2,15}, {2,17}, {2,19}, {2, 20}, {3,11}, {3,12}, {3,13}, {3,14}, {3,15}, {3,16}, {3,18}, {4,14}, {4,15}, {4,16}, {4,17}, {4,18}, {4,19}, {4, 20}, {5,11}, {5,12}, {5,13}, {5,15}, {5,17}, {5,18}, {5, 20}, {6,12}, {6,16}, {6,17}, {6,18}, {6,19}, {6, 20}, {7,11}, {7,12}, {7,13}, {7,14}, {7,16}, {7,17}, {7,19}, {8,11}, {8,12}, {8,13}, {8,14}, {8,15}, {8,18}, {8,19}, {8, 20}, {9,11}, {9,14}, {9,15}, {9,16}, {9,17}, {9,18}, {9,19}, {10,11}, {10,13}, {10,15}, Then, e(G') = 4203 > 4176. Acknowledgment. The authors are grateful to an anonymous referee for useful suggestions, and helpful comments. References [1] T. Hibi, N. Li and Y. X. Zhang, Separating hyperplanes of edge polytopes, J. Combin. Theory Ser. A 120 (2013), 218-231, doi:10.1016/j.jcta.2012.08.002. [2] H. Ohsugi and T. Hibi, Normal polytopes arising from finite graphs, J. Algebra 207 (1998), 409-426, doi:10.1006/jabr.1998.7476. [3] H. Ohsugi and T. Hibi, Toric ideals generated by quadratic binomials, J. Algebra 218 (1999), 509-527, doi:10.1006/jabr.1999.7918. [4] H. Ohsugi and T. Hibi, Compressed polytopes, initial ideals and complete multipartite graphs, Illinois J. Math. 44 (2000), 391-406. [5] H. Ohsugi and T. Hibi, Simple polytopes arising from finite graphs, in: Proceedings of the 2008 International Conference on Information Theory and Statistical Learning (ITSL), 2008 pp. 7379, (available at http://arxiv.org/abs/0 804.428 7). [6] T. Tran and G. M. Ziegler, Extremal edge polytopes, Electron. J. Combin. 21 (2014), Paper 2.57, 16. G g O2o and each non-empty connected component of G is a complete bipartite graph {10,16}, {10,18}, {10,19}, {10, 20}}.