IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1157 ISSN 2232-2094 EULER'S IDONEAL NUMBERS AND AN INEQUALITY CONCERNING MINIMAL GRAPHS WITH A PRESCRIBED NUMBER OF SPANNING TREES Jernej Azarija Riste Skrekovski Ljubljana, August 16, 2011 VD CO CO CD Jh Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees Jernej Azarija Riste Skrekovski Department of Mathematics, University of Ljubljana, Jadranska 21, 1000 Ljubljana, Slovenia {jernej.azarija,skrekovski}@gmail.com O July 17, 2011 Abstract Let a(n) be the least number k for which there exists a simple graph with k vertices having precisely n > 3 spanning trees. Similarly, define ^(n) as the least number k for which there exists a simple graph with k edges having precisely n > 3 spanning trees. As an n-cycle has exactly n spanning trees, it follows that a(n),@(n) < n. In this paper, we show that a(n) < n^4 and @(n) < ^J7 if and only if n {3, 4, 5,6, 7,9,10,13,18,22}, which is a subset of Euler's idoneal numbers. Moreover, if n ^ 2 (mod 3) and n = 25 we show that a(n) < nJ9 and P(n) < . This improves some previously known bounds. 1 Introduction Results related to the problem of counting spanning trees for a graph date back to 1847. In [6], Kirchhoff showed that the number of spanning trees of a graph G is closely related to the cofactor of the Laplacian matrix of G. Since then, a number of related results followed. In 1889, Cayley [2] derived the number of spanning trees for the complete graph on n vertices which is nn-2. Since then formulas for various families of graphs has been derived. For example, it was shown by Baron et al. [1] that the number of spanning trees of the square of a cycle Cn equals to nFn where Fn is the n'th Fibonacci number. Speaking about a seemingly unrelated branch of mathematics, Euler studied arround 1778 a special class of numbers allowing him to find large primes. He called such numbers idoneal numbers (numerus idoneus). He was able to find 65 such numbers I = {1, 2, 3, 4, 5, 6, 7, 8, 9,10,12,13,15,16,18, 21, 22, 24, 25, 28, 30, 33, 37, 40,42, 45, 48, 57, cu { CM r vO 2 58,60,70, 72, 78,85, 88, 93,102,105,112,120,130,133,165,168,177,190,210,232,240,253, 273, 280, 312, 330, 345, 357, 385,408,462,520, 760,840,1320,1365,1848}, see also [9]. Gauss [5] later conjectured that the set of idoneal numbers I is complete. It was later proved by Chowla [3] that the set of idoneal numbers is finite. We denote by I * the set of idoneal numbers not present in I and remark that if the Generalized Riemann Hypothesis is true, then I * = 0 [10]. It is also known that any idoneal number in I * has at least six odd prime factors [4]. In this paper we use the definition of idoneal numbers stating that n is idoneal if and only if n is not expressible as n = ab + ac + bc for integers 0 < a < b < c. For other characterisations of idoneal numbers see [11]. We use this number theoretical result to improve the answer related to the question Sedlacek [7] posed in 1970: Given a number n > 3 what is the least number k such that there exists a graph on k vertices having precisely n spanning trees? Sedlacek denoted this function by a(n). He was able to show that a(n) < np for almost all numbers. More precisely he proved that a(n) < n + 2 whenever n = 0 (mod 3) and a(n) < n^4 whenever n = 2 (mod 3). Nebresky [8] later showed that the only fixed points of a(n) are 3, 4, 5, 6, 7,10,13 and 22, i.e. these are the only numbers n such that a(n) = n. He also defined the function P(n) as the least number of edges l for which there exists a graph with l edges and with precisely n spanning trees. He showed that n + 1 a(n) t(G) + 2 and t(G + Pfc) > k t(G) (2) CM r vO 2 for a connected graph G and k > 2. The first inequality follows from the fact that we can form at least two spanning trees in G + e that are not spanning trees in G by taking a spanning tree T of G and obtain new trees T1, T2 after removing an edge (not equal to e) from the cycle that is obtained in T + e. The second inequality is equally easy to prove. Graphs with a(n) vertices with n spanning trees poses some structure. For example, it follows directly from equation (1) that graphs having n spanning trees with a(n) vertices are always 2-edge-connected. A simple argument can then be used to show that such graphs have cycles of length at most n provided that a(n) < n. For nonnegative integers a, b, c, let 6a ,b, c be the graph comprised of two vertices connected by three internally disjoint paths of length a, b and c, respectively. We refer to these paths as Pa, Pb and Pc. Note that 6a,b,c is simple if and only if at most one of a, b, c equals 1. For a, b > 3 denote by Ca,b the graph obtained after identifing a vertex of an a-cycle with a vertex of a disjoint b-cycle. Notice that 6a,b,0 is isomorphic to Ca,b. lO 2 Lower bounds for the number of spanning trees of graphs derived from 0abc In this section, we examine the number of spanning trees that arise in 6a,b,c when interconnecting two distinct vertices by a disjoint path of length d. In order to do so we define simple graphs 6^ bc d(ai,a2), 6^ bc d(ai), 6^ bc d(ai,bi) that are obtained from 6a , b, c by introducing a path. Let u,v be the 3-vertices of 6a , b, c. First we construct 60. We assume a > 3. For integers a1 > 1 and a2 > 1 with a1 + a2 < a, let x and y be the vertices of Pa such that dPa (u, x) = a1 and dPa(v, y) = a2. Then 6^bcd(a1,a2) is the graph obtained by interconnecting x and y with a disjoint path of length d, see the first graph of Figure 1. As we are only dealing with simple graphs we require that d > 1 if a1 + a2 = a — 1. We now construct 61. Let x = u and let y be a vertex on Pa such that dPa (u, y) = a1 > 1. Then 6^ b c d(a1) is the graph obtained by interconnecting x and y by a disjoint CO path of length d. See the second graph of Figure 1. Notice that the possibility y = v is not excluded; in that case 6^, b, c, d(a1) has two 4-vertices. Since we wish that the resulting graph is simple we requre d > 2 whenever a1 = 1 and d > 2 whenever min(a, b, c) = 1. Moreover we assume a > 2. Finally, define 6a,bc,d(a1, b1) by choosing a vertex x on Pa, x 1 and b1 > 1. Then, 6^bcd(a1,b1) is the graph obtained by connecting x and y by a disjoint path of length d as shown on the third graph of Figure 1. Observe that this construction requires a,b > 2, a — a1 > 1, and b — b1 > 1 in order to preserve simplicity of 62. We now present some formulas and inequalities for the number of spanning trees for the graphs we just defined. The following equalities are easy to derive using equation (1). Jh Lemma 1. The following three equalities hold: CD U CU (1). t(6^b c d(a1,a2)) = dr(6aAc) + (a — a')t(6a/ ,b,c) where a1 + a2 = a', VD CO 2 Figure 1: Graphs ©a bcd(a^a2), ©a bcd(ai), ©a bcd(ai,bi) obtained after adding a path of length d between two distinct vertices x, y of 6a,b, c. 0 o 1 CO ^ CO CO CO CD $H CD CO u a CD U (2). T (6lb,c,d(a 1)) = dr (6a, b , c) + a1 r (6a-ai ,b,c); (3). T(©a,b,c,d(ai, bi)) = dr(6a,b,c) + c(ai + 6i)(a2 + 62) + a^6 + 6162a where a2 = a — ai and 62 = 6 — 6i. We use the identities presented in Lemma 1 in order to derive some lower bounds for the number of spanning trees for the graphs 60, 6i and ©2. Lemma 2. It holds r(©abcd(ai,a2)) > ( (d + 2) f a = 3 0rd 7 2' v a , b, c, d\ ^ 2>) (d + 1) r(©a b, c) if a > 4 and d = 1. Proof. Let p(x) = (a — x)(6c + x(6 + c)). By Lemma 1.(1) we have to show: ir(6a ,b,c) if a = 3 or d > 2, P(x) > ( T(6a,b,c) if a > 4 and d =1. where x = ai + a2 As p is a quadratic concave function it is enough to verify the claim for x G {2, a — 1} if d > 2 and x G {2, a — 2} if d =1. Suppose first that x = 2, i.e. ai = a2 = 1. If a = 3 then p(2) = 6c + 26 + 2c > 2 (36 + 3c + 6c) = 2r(6a,b,c) and if a > 4, then p(2) = a6c + 2a6 + 2ac — 26c — 46 — 4c > (6c + a6 + ac) + (36c — 26c + a6 + ac — 46 — 4c) > a6 + ac + 6c = T (©a,b,c). Suppose now that d > 2 and x = a — 1. Then, we have p(a — 1) = 6c + (a — 1)(6 + c) > 2 (a6 + ac + 6c) as a > 3. Finally assume d =1 and hence a > 4. Then, p(a — 2) = 26c + 2(a — 2)6 + 2(a — 2)c > a6 + 6c + ac as 2(a — 2) > a. □ o CSF 2 2 IN lO O Ö CO CD $H CO Jh a CD U Lemma 3. It holds T(ei)6)c)d)(ai) > (d + 1)t(eaAc). Proof. By Lemma 1.(2) it is enough to show p(x) > 2(ab + ac + bc) for each x E [1, a], where p(x) = x(bc + b(a — x) + c(a — x)). As p is a quadratic concave function, it is enough to show this inequality only for x =1 and x = a. For x = 1, this inequality reduces to ab + bc + ac > 2c + 2b which trivially holds for a > 2. For x = a, we have to show the inequality abc > 2(ab + bc + ac). Notice that a > 2 and at least one of b,c is > 2, say b. Then ab > a + b and hence: 2abc > (a + b)c + abc > ab + bc + ac. Lemma 4. It holds T(eaAC)d)(ai,bi) > (d + 1) T(eaAc). Proof. By Lemma 1.(3), we have to show that c(a1 + b1)(a2 + b2) + a1a2b + b1b2a > ac + bc + ab. □ It will be enough if we show that: o (a1 + b1)(a2 + b2) > a + b and a1a2b + b1b2a > ab. The first inequality follows immediately by the known fact xy > x + y for x,y > 2 (just set x = ai + bi and y = a2 + b2). 6 as CM For the second inequality, it is enough to observe that a1a2 > | and b1 b2 > 2 xy > whenever x,y > 1. □ Using the derived bounds from Lemmas 2.-4. we can state the following Corollary CO that turns out to be useful in the next section. HH Corollary 1. Let G be the graph obtained after interconnecting two vertices of Oa,b,c with a d-path (d > 1). Then 3t(Ba)b,c)/2 d =1, T(G) >4 5t(Ba)b,c)/2 d =2, 3t(@a,b,c) d > 3. Proof. Let G be the graph obtained after interconnecting two vertices x, y of Oa,b,c with a d-path. If d = 1 or d = 2 then x and y are distinct and we see from Lemmas 2, 3 and 4 that the stated inequality holds. If d > 3 and x, y are distinct it follows from Lemmas 2.-4. that the number of spanning trees of G is at least 2 times greater than t(©a,b,c). However, if x = y then we obtain a graph that has Cd and Oa,b,c as blocks and thus t(G) = dT(©a,b,c) > 3t(@a)b,c) which implies our claim. □ 3 Inequality with functions a and P This section presents our main result. We derive some bounds and equalities for a and P for some small values and afterwards we show that for n ^ 2 (mod 3) GÏ O CM i 00 CM CM u CD CO s n +13 P (n) < W) <—4 — 1 1—1 except for a few cases. CO Proposition 1. a(22) = p(22) = 22. M Proof. It is enough to show a(22) = 22. Let us assume G is a graph on |V(G)| < 22 vertices with precisely 22 spanning trees. Since 22 is not expressible as ab + ac + bc for a > 1, b, c > 2 and since it is not expressible as 22 = ab for a, b > 3 it follows that there exist integers a > 1 and b, c > 2 such that ©a,b,c C G. The only ©'s graph having less than 22 spanning trees and vertices are 61,2,2, ©1,2,3, ©2,2,2, ©1,2,4, ©1,3,3, ©2,3,3, ©2,2,3, ©1,2,5, ©1,3,4, ©1,2,6 and ©2,2,4, so G contains at least one of them. Moreover we see from Corollary 1 that introducing a d-path (d > 1) to any of the graphs ©1,3,3, ©2,3,3, ©2,2,3, ©1,2,5, ©1,3,4, ©1,2,6 or ©2,2,4 yields a graph with at least 1 = 23 spanning trees. Thus we can conclude that ©1,2,2, ©1,2,3, ©2,2,2 or ©1,2,4 is a proper subgraph of G. Assume ©1,2,2 C G. Since ©1,2,2 has four vertices and since any graph on four vertices has at most 16 spanning trees it follows that there exists a subgraph F of G that is obtained after interconnecting two vertices of ©1,2,2 with some k-path (k > 1). If k > 3 then from Corollary 1 we have that F is a graph with at least 8 ■ 3 > 22 spanning CM trees, so k = 2. Observe that this implies that we can assume ©2,2,2 C G, ©1,2,3 C G or ©12,4 C G. Moreover, using Corollary 1 we see that by adding a d-path (d > 2) to any of the graphs ©1,2,3, ©2,2,2, ©1,2,4 one obtains a graph with at least ^] = 28 spanning trees. Combining these two facts we conclude that G' + e C G for an edge e and G' e {©1,2,3, ©2,2,2, ©1,2,4}. CO After consulting Table 1 we see that all such graphs G' + e have more than 22 spanning trees with the exception of ©2,2,2,1(2) and ©3,2,1,1 (2) which have 20 and 21 spanning trees, respectively. We now deduce from inequality (2) that H = ©2,2,2,1(2) + e' C G for an edge e' since the addition of an edge or a path to ©3,2,1,1(2) produces a graph with at least 23 spanning trees while introducing a > 2-path to ©2,2,2,1(2) yields a graph having at least 40 spanning trees. Using the recurrence (1) we see that t-H T(G) > T(H - e') + T(H/e') > t(©1,2,2,1(2)) + t(©1,2,2) = 28 m since ©1,2,2 C H/e' regardless of the choice of e'. The following implies that there is no graph having 22 spanning trees and less than 22 vertices, thus proving the stated lemma. □ Proposition 2. The following holds P(9) = 6, a(18) = 8, a(25) > 9, P(37) < 9, P(58) < 10, P(30) < 8. Proof. We consider each claim individually: vo CO M < IN 0 o CM 1 CM CO CM CM £ CO CO CO CD $H CD CO $H a CD U G G + e Number of spanning trees ©1,2,3 ©1,2,I,I(2) ©3,2,I,I(1, 1) 21 24 ©1,2,4 ©1,2,I,I(2) ©4,2,I,I(1, 1) ©4,2,I,I(2, 1) ©4,2,I,I(1, 1) 30 32 35 30 ©1,3,3 ©1,3,I,I(2) ©3,3,I,I(1, 1) ©3,3,I,I(1, 2) 29 35 36 ©2,2,2 ©2,2,2,1(1,1) ©2,2,2,1 (2) 24 20 ©2,2,3 ©3,2,2,1 (2) ©3,2,2,1(1, 1) ©2,2,3,1(1, 1) 32 35 32 Table 1: Graphs constructed in the proof of Proposition 2 and Theorem 5. • ^(9) = 6. It is easy to verify that there is no graph on < 5 edges or less with 9 spanning trees and that t(C3,3) = 9. • fl(30) < 8. We see from the first equality in Lemma 1 that ©4,1,2,1(1,1) has 30 spanning trees and 8 edges from where the stated inequality follows. • fl(37) > 9. According to the second identity stated in Lemma 1, t(©3,1,4,1 (2)) = 37. This implies ^(37) < 9 since ©3,1,4,1(2)(1,1) has 9 edges. • fl(58) < 10. From the second identity derived in Lemma 1 we see that ©4,3,2,1 (2) is a graph with 10 edges having precisely 58 spanning trees which implies ^(58) < 10. • a(25) = 9. Clearly, 65,5 is graph of order 9 with 25 spanning trees. Assume now a(25) < 8 and let G be a graph with 25 spanning trees having less than 9 vertices. The only graph of the form Ca,b which has 25 spanning trees is C5,5 but |V(C5,5)| = 9. Moreover, there do not exist integers a > 1, b, c > 2 such that |V(©a,b,c)| < 9 and t(©a,b,c) = 25. Thus, it follows that G contains as a subgraph some ©a,b,c with at most 8 vertices, i.e a + b + c < 9. It can be verified that adding a d-path (d > 1) to all such graphs produces a graph with at least 25 spanning trees with the exception of the graphs ©1,2,2, ©1,2,3, ©1,2,4, ©1,3,3, ©2,2,2, ©2,2,3. Moreover we see from Corollary 1 that adding a 2-path to the graph ©a,b,c yields a graph with at least |t(©a,b,c) spanning tees. We now split the proof into two cases: Case 1: ©1,2,3, ©1,2,4, ©1,3,3,©2,2,2 or ©2,2,3 is a subgraph of G. By the above observation, adding a 2-path to any of the graphs covered in this case produces a graph with at least 2 ■ 11 > 25 spanning trees. Thus G' + e C G for G' E {©1,2,3, ©1,2,4, ©1,3,3, ©2,2,2, ©2,2,3} and an edge e. Table 1 lists all the graphs (up to isomorphism) and the respective number of spanning trees CM e vO that can be constructed after adding an edge to G'. The fact that adding an edge or a path to a connected graph increases its number of spanning trees by at least 2 reduces our choice for G' to the elements of the set 2,2,1 (2), ©3,2,1,1 (2)}. Moreover we saw in the proof of Proposition 1 that t(©2,2,2,1 (2) + e') > 28 for any edge e'. As we cannot add a > 2-path to ©2,2,2,1 (2) without obtaining a graph with less than 40 spanning trees (by the second inequality stated in (2), it follows that G C H = ©3,2,1,1(2) + e' for an edge e'. Using the deletion-contraction recurrence stated in (1), we now see that t(G) > t(H - e') + t(H/e') > t(©1,2,1,1 (2)) + t(©1,2,2), since the graph H/e' contains ©1,2,2 as a subgraph independently of the choice of e'. IN Case 2: ©1,2,2 is a subgraph of G. Observe that ©1,2,2 + e = K4 and t(K4) = 16. Moreover, we see from Lemmas 2.-4. that adding a 3-path to ©1,2,2 produces a graph with at least 3 ■ 8 > 25 spanning trees unless the path interconnects the same vertex in which case we obtain a graph H with 3 ■ 8 = 24 spanning trees. Observe, that a similar argument holds when we add a longer path to ©12 2. Since from inequality (2) we cannot introduce an edge or a path to H that would produce a graph with less than 26 spanning trees we conclude that G = ©1,2,2,2 for i E (0,1,2}. But this implies that ©2,2,2 C G or ©1,2,3 C G and we can use the same reasoning as in Case 1 to conclude that there is no graph G satisifying the stated properties. CM The proof of the stated inequality is now complete since the above two cases show that there does not exist a graph on less than 9 vertices that has 25 spanning trees. o CM £ CO CO • a(18) = 8. Since t(C3,6) = 18, it follows that a(18) < 8. To prove that a(18) > 8 and thus a(18) = 8. One can now use a similar argument as in the previous case a(25) = 9. ~ □ Proposition 3. If n G {40, 42, 45, 48, 60, 70, 72, 78, 85, 88,102,105,112,120,130,133, 165,168,190,210,232,240,253,273,280,312,330,345,357,385,408,462,520,760,840,1320, 1365,1848} U I * then £ (n) < ^. Proof. Let n be a number from the set defined in the statement of this lemma. If n is of the form n = 5k for k > 7 then |E(©5,k)| < ^^p3 since 5 + k < 5k+13 for every k > 7. Therefore, the inequality holds for every n divisible by 5 since every such n that is in the list satisify the required condition. The same reasoning can be applied to the cases when n is a divisor of 6 or a divisor of 7 leaving us to verify the inequalities for the numbers n G {88, 232, 253} U I*. It is easy to verify that for n G {88, 232, 253} the graphs ©8,n, ©s,29, ©n,23 have 88, 232 and 253 spanning trees, respectively and that the inequalities on the number of edges and vertices are satisifed. If n G I * then we use the fact that n has at least three odd prime factors. Let p1,p2 be two of these prime factors of n and let d = p^. We construct the graph C by taking CD CO disjoint cycles CP1, Cp2, Cd and identifing a vertex of every cycle observe that the graph is well defined as d > 3. The obtained graph clearly has n spanning trees and i—l o Pl +P2 + d < s + 3 + 9 < edges. The last inequality following from the fact that n is clearly greather than 30. □ Theorem 5. Let n > 3 be an integer. Then, ft(n) < if and only if n ©2,2,6, ©3,3,^ ©3,3^ ©3,3,14, ©3,3,28 have 8, 12, 15, 16, 21, 24, 28, 33, 57, 93 and 177 spanning trees respectively while also satisfying the stated inequality for the number edges. 00 We are now left with the idoneal numbers 9, 18, 25, 30, 37 and 58. We see from Proposition 2 that for n e {30, 37,58} the inequality holds and that for n e {9,18, 25} the inequality does not hold which now proves our theorem. □ CO CO Generalizing the graph ©a,b,c to the graph containing four disjoint paths of length a, b, c, d that interconnect two vertices, one obtains a graph with abc + abd + acd + bcd spanning trees. Using this generalisation for a higher number of disjoint paths one could lower the constant factor in our inequality to an arbitrary amount. The fact that there is no result known to the authors, related to the solvability of the respective equations and the fact that there could exist a superior construction yielding a better lower bound, motivates the following question: m Question 1. Given a real number c > 0 is there a no such that for every n > no it holds a(n) < cn? £ References iH & [1] G. Baron, F. Boesch, H. Prodinger, R. Tichy and J. Wang, The Number of Spanning Trees in the Square of Cycle, The Fibonacci Quart., 23 (1985) 258-264. vo CO 2 IN lO 0 Ö o CM 1 CM CO CM CM £ CO CO [2] G. A. Cayley, A theorem on trees, Quart. J. Math 23 (1889) 276-378. [3] S. Chowla, An extension of Heilbronn's class number theorem, Quart. J. Math. 5 (1934) 304-307. [4] P. Clark, Private communication, http://mathoverflow.net/questions/20955/ the-missing-euler-idoneal-numbers [5] C. F. Gauss, Disquisitiones Arithmeticae, Translated by A.A. Clarke, 1966, Springer-Verlag, New York, 1986. [6] G. G. Kirchhoff, Uber die auflosung der gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer strme gefhrt wird, Ann. Phy. Chem. 72 (1847) 497-508. [7] J. Sedlacek, On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515-517. [8] L. Nebresky, On the minimum number of vertices and edges in a graph with a given number of spanning trees, Cas. Pest. Mat. 91 (1971) 95-97. [9] A. Weil, Number Theory: An Approach Through History, Birkhauser, Boston, Basel and Stuttgart, 1984. [10] P. Weinberger, Exponents of the class groups of complex quadratic fields, Acta Arith. 22 (1973) 117-124. [11] E. W. Wesstein, Idoneal Number, MathWorld-A Wolfram Web Resource, http: //mathworld.wolfram.com/IdonealNumber.html CO CD Jh CD CO u a CD U