A257637 Maximal number of edges in an n-vertex triangle-free graph with maximal degree at most 4.

0, 1, 2, 4, 6, 9, 12, 16, 17, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120

Offset: 1

Author

Jörgen Backelin, Nov 04 2015

Keywords

• easy
• nonn

Comments

For n <= 8, a(n) is the Turan number T(3,n), realized by a complete bipartite graph K(m, m) if n = 2m or K(m, m+1) if n = 2m+1, since then that graph has maximal degree <= 4.

For n >= 10, any 4-regular triangle-free graph (i.e., graph with no three-cliques) will do.

For n = 9, there is no 4-regular triangle-free graph, as can be seen from inspection.

Links

• Jörgen Backelin, Table of n, a(n) for n = 1..100
• Index entries for linear recurrences with constant coefficients, signature (2,-1).

Crossrefs

Cf. A002620, A005843.

Programs

PARI

a(n)=if(n>9, 2*n, if(n<9, n^2\4, 17)) \\ Charles R Greathouse IV, Jan 06 2016

Formula

a(n) = floor(n^2/4) = A002620(n), if 1 <= n <= 8.

a(9) = 17.

a(n) = 2*n = A005843(n), if n >= 10.

From Chai Wah Wu, Feb 03 2021: (Start)

a(n) = 2*a(n-1) - a(n-2) for n > 11.

G.f.: x*(-x^10 + 2*x^9 - 3*x^8 + x^7 + x^5 + x^3 + x)/(x - 1)^2. (End)