Edge number critical triangle free graphs with low independence numbers

Jörgen Backelin

September 30, 2013

Abstract

The structure of all triangle free graphs G = (V, E) with |E|−6|V |+α(G) = 0 is determined, yielding an affirmative answer to a question of Stanisław Radziszowsky and Donald Kreher.

Keywords: Linear graph invariant; independence number; e-number; edge number critical graph; edge critical graph; triangle free graph.

1 Background.

A graph is edge number critical (under certain conditions), if it has the minimal possible number of edges for all graphs fulfilling these conditions. In this article, some edge number critical graphs are determined among the triangle free graphs (graphs without K_{3} subgraphs) with a prescribed number of vertices, upper bound for the independence number, and sometimes also a prescribed minimal valency.

In my opinion, characterising such graphs has some interest in itself. Moreover, often it is crucial for determining better bounds for Ramsey numbers.

In 1991, in [5], Radziszowski and Kreher proved that

(1)  |E| − 6 |V | + 13 α(G) ⩾ 0

for any triangle free simple graph G = (V, E), where α(G) is the independence number of G. They also described some graphs for which equality in (1) is attained, and suggested that there might be no other such graphs.

Actually, (1) is one of a series of ‘linear inequalities’, which starts by

\begin{matrix}|E| & ⩾ & 0, \\ |E| − |V | + α(G) & ⩾ & 0, \\ |E| − 3 |V | + 5 α(G) & ⩾ & 0, and \\ |E| − 5 |V | + 10 α(G) & ⩾ & 0 . \end{matrix}

For each one of these ‘earlier’ inequalities, the graphs for which equality holds are edge number critical (with respect to triangle freeness and to vertex numbers and independence number upper bounds), and they have been classified explicitly, mainly by Radziszowski and Kreher; see e. g. propositions 2.2 and 6.3 in [5].

Some years later, I was able to confirm Radziszowski’s and Kreher’s conjecture, and included a proof in my book manuscript Contributions to a Ramsey calculus [1]. Thus, the inequality (1) is strict for all other triangle free graphs. This consequence was quoted and employed in 2000 by Lesser [3]. However, my still far from finished manuscript, and thus the proof, have remained unpublished. It has been pointed out to me that this is a non-optimal state of matter. I therefore decided to present the proof in a ‘stand-alone’ article.

However, just reproducing the proof from my manuscript [1] together with all its dependencies, would amount to an unproportionally large article. I am trying to make [1] as self-contained as possible, but on the other hand its proofs do contain numerous internal references to more general results with multiple applications. On the other hand, in the present article, shortcuts are possible, largely due to the possibility to refer to [5], where in fact a considerable part of the necessary ground work is done.

This article thus has a dual character. The concepts, terminology, and notation largely follow my manuscript, but the proofs as far as reasonably possible are simplified by recycling the [5] arguments and results. In particular, it in no ways should depend on unpublished results, except in the broader discussion in section 7 at the end, and in some of the footnotes in the earlier sections (none of which contains facts used in the proofs there).

2 Fundamental concepts and notation.

2.1 Basics.

Throughout this article, all considered graphs are undirected, simple, and finite; thus, formally, a graph is a pair (V, E) of finite sets, such that every element of E is a 2-subset of V. In other words, we demand that the cardinality |V | < ∞, and that

E ⊆ \binom{V}{2} = \{V subsets of cardinality 2\}.

If G = (V, E) we also let V (G) = V and E(G) = E.

It will be convenient not to disconsider the empty graph, formally the pair (∅, ∅), but in shorthand represented just by ∅. Similarly, here the natural numbers be N = {0, 1, 2, 3, …} (including zero).

When we consider a fixed graph G = (V, E), the shorthand notation often is extended to arbitrary subsets of V; W ⊆ V sometimes also may be used for the induced subgraph (W, E_{W}), where E_{W} in its turn is shorthand for E ∩ \binom{W}{2}. If W and X are two subsets of V, then

E_{W,X} = {{w, x} ∈ E : w ∈ W ∧ x ∈ X} .

Recall that an isomorphism between two graphs (V, E) and (V′, E′) is a bijection between V and V′ which induces a bijection between E and E′; let G ≃ G′ denote either an isomorphism, or just the fact that G and G′ are isomorphic, depending on the context. If moreover v_{1}, …, v_{r} and w_{1}, …, w_{r} are sequences of vertices in G and G′, respectively, then (G, v_{1}, …, v_{r}) ≃ (G′, w_{1}, …, w_{r}) denotes a relative isomorphism, i. e., an isomorphism which furthermore maps v_{i} to w_{i} for i = 1, …, r, or the existence of such an isomorphism.

There are numerous classes of graphs, which technically are only defined up to isomorphisms. By a slight abuse of terminology, often a graph will be used, where more correctly an isomorphism class of graphs should be treated. Likewise, = (equal to) may be used, where technically ≃ (isomorphic to) would be more correct.

As usual, K_{i} and C_{i} denote ‘the’ complete graph (or properly: a complete graph) and ‘the’ cycle graph on i vertices, respectively. In general, let V (K_{i}) = {k_{1}, …, k_{i}} and V (C_{i}) = {c_{1}, …, c_{i}}. P_{i} denotes ‘the’ path graph with i vertices (and thus i − 1 edges). K_{i,j} is the complete bipartite graph with i and j vertices in the respective parts. If different copies of these or other graphs defined up to isomorphism are needed in the same context, they are distinguished by primes; as in C_{5}, C′_{5}, C′′_{5}, … for different 5-cycles.

In this article the sum of two graphs is their disjoint union; in other words, for G = (V, E) and G′ = (V′, E′) with V ∩ V′ = ∅, we put G + G′ = (V ∪ V′, E ∪ E′); while, if V ∩ V′ ≠ ∅, G + G′ only is defined up to isomorphism, as the sum G′′ + G′′′ for any G′′ ≃ G and G′′′ ≃ G′, such that V (G′′) ∩ V (G′′′) = ∅. For any m ∈ N and any graph G, mG is the sum of m copies of G; in particular, 0G = ∅ and 1G = G.

A graph G = (V, E) is edge critical, if the removal of any edge increases the independence number, i.e., if α((V, E′)) > α(G) for every proper subset E′ of E. If it is not edge critical, then there is some edge ε ∈ E, which is redundant, i. e., such that α((V, E \ {ε})) = α(G).

As usual, the distance dist(v, w) between two vertices is the smallest number of edges in any path connecting them, if there is one, and ∞ else.

The link of a vertex v in a graph G = (V, E) is (the induced subgraph on) the set of vertices adjacent to v: lk v = lk_{G}(v) = {w ∈ V : {v, w} ∈ E} = {w ∈ V : dist(v, w) = 1}^{1}. (Here and in the sequel, denoting the graph may be omitted, if it is clear from the context.) The (first) valency of v is d(v) = d_{G}(v) = |lk v|. The second valency of v is the sum of all first valencies of its neighbours:

d^{2}(v) = d_{G}^{2}(v) = d(lk v) := ∑_{w∈lk v} d(w) .

For v ∈ V and d ∈ N, the d-neighbourhood of v or the ball of radius d and centre v is B(v; d) = B(G, v; d) = {w ∈ V : dist(v, w) ⩽ d}. For S = {v_{1}, …, v_{r}} ⊆ V,

1Graphs may be considered as (the 1-skeletons of) flag abstract simplicial complexes. From this point of view, the link of a 0-simplex {v}, in its usual sense, is precisely lk v.

the electronic journal of combinatorics 16 (2009), #R00 3

B(S; d) = B(G, S; d) = B(v_{1}, …, v_{r}; d) = B(G, v_{1}, …, v_{r}; d) = ⋃_{j=1}^{r} B(v_{j}; d) .

A monovalent (bivalent, trivalent, et cetera) (vertex) is a vertex of valency 1 (2, 3, et cetera, respectively).

2.2 Invariants.

Recall that a (proper) graph invariant is a number valued function f on the set of all (finite et cetera) graphs, such that

G ≃ G′ ⟹ f(G) = f(G′) .

The invariant f is linear, if in addition it ‘respects sums’, i. e., if

f(G + H) = f(G) + f(H), ∀ G, H .

In particular, then clearly f(mG) = mf(G), and f(∅) = 0.

A generalised graph invariant is defined similarly, but some of the values may be nonnumbers. (We do not consider any kind of linearity condition for non-proper invariants.) An example is the girth,

girth(G) := inf{i : N(C_{i}|G) ≠ 0};

thus, by the usual convention for infima of empty sets of natural numbers, girth(G) = ∞ if and only if G is acyclic, i. e., is a forest.

A linear inequality is an inequality f(G) ⩾ g(G) involving two linear graph invariants f and g, and which holds for all graphs of some specified class, which is closed under addition.

For two graphs H and G, let the number of occurrences of H in G, N(H|G), be the number of G subgraphs G′ (induced or not), such that G′ ≃ H. There is also a relative variant: For u_{1}, …, u_{r} ∈ V (H) and v_{1}, …, v_{r} ∈ V (G), N(H, u_{1}, …, u_{r}|G, v_{1}, …, v_{r}) denotes the number of subgraphs of G which are isomorphic to H relatively the u_{i} mapping to the v_{i}. If there is no possible ambiguity, the u_{1}, …, u_{r} may be omitted. Thus, N(C_{i}|G, v) = N(C_{i}, c_{1}|G, v) or N(C_{i}, c_{1}, c_{2}|G, v, w) is the number of i-cycles through a vertex v or an edge {v, w} in G, respectively.

Note, that N(H|G) is a graph invariant (with respect to G), for any fixed H. This invariant is linear if and only if H is connected. Two such linear invariants are

n(G) = N(K_{1}|G) = |V (G)| and e(G) = N(K_{2}|G) = |E(G)| .

For each natural number d, the number of d-valents is a graph invariant, denoted #d(G).

Another important linear graph invariant is the independence number, the maximal size of an independent subset of vertices:

α(G) = max (|S| : S ⊆ V ∧ \binom{S}{2} ∩ E = ∅) .

Likewise, the number comp(G) of (connected) components of G is a linear graph invariant. On the other hand, the clique number ω(G) = max (i : N(K_{i}|G) > 0) is a graph invariant, but not linear. In fact, ω(G + H) = max (ω(G), ω(H)). (ω(∅) = 0.)

The graph G is triangle free, if ω(G) ⩽ 2, or, equivalently, if girth(G) ⩾ 4. In the later sections of this article, we only consider triangle free graphs. The triangle free graph G is square free, if in addition it does not contain any 4-cycle (or “square”), or, equivalently, if girth(G) ⩾ 5.

Directly from the definitions we get

Lemma 2.1. A linear combination of linear graph invariants is itself a linear graph invariant. □

In this article, the two most important linear invariants formed as linear combinations are

t(G) := ℓ_{6}(G) = e(G)−6n(G)+13 α(G) and q(G) := ℓ_{5}(G) = e(G)−5n(G)+10 α(G) .

2.3 Independence stability.

A destabilising subset or destabiliser M in a graph G = (V, E) is a subset of V, such that the induced subgraph on V \ M has a lower independence number than α(G). The graph G is s-stable, if it has no destabiliser of size ⩽ s, and is strongly s-stable, if in addition no destabilising subset of size s + 1 is independent. (Often, the induced subgraph on M also is called M.) Now, if v ∈ V = V (G), and S is an independent subset of V \ B(v; 1), then S ∪ {v} also is independent; whence we directly get

Lemma 2.2. For any vertex v in a graph G, B(G, v; 1) destabilises G. □

If S = {v_{1}, …, v_{r}} is an independent subset of G = (V, E), then

G_{v_{1},...,v_{r}} = (V_{v_{1},...,v_{r}}, E_{v_{1},...,v_{r}})

denotes the induced subgraph on everything but the neighbourhood of S; in other words, V_{v_{1},...,v_{r}} = V \ B(G, S; 1) and E_{v_{1},...,v_{r}} = E ∩ \binom{V_{v_{1},...,vr}}{2}. (Whenever we employ the notation G_{v_{1},...,v_{r}}, we indeed assume that the v_{i} are different and form an independent set.) Since obviously

G_{v_{1},...,v_{r}} = (⋯ ((G_{v_{1}})_{v_{2}}) ⋯)_{v_{r}},

and by inductive use of lemma 2.2, we have

Lemma 2.3. α(G_{v_{1},...,v_{r}}) ⩽ α(G) − r. □

In some interesting situations, we have equality.

Lemma 2.4. If G = (V, E) is edge critical and v ∈ V, then α(G_{v}) = α(G) − 1.

Proof. This is immediate from the linearity, if d(v) = 0, since then G = {v}+(V \{v}, E).

Else, choose a w ∈ lk v, and let k = α(G) and E′ = E \ {{v, w}} ⊂ E. By the edge criticality, there is a (k + 1)-subset S of V, which is independent in (V, E′). Now, if S did not contain both v and w, it were independent in G as well, against the assumptions. Thus, instead, v, w ∈ S, and S \ {v, w} is an independent (k − 1)-subset of G_{v}.

Thus, α(G_{v}) ⩾ k − 1 = α(G) − 1, whence we indeed have equality by lemma 2.3.

Obviously, n(G_{v}) = n(G) − d(v) − 1. Moreover, if N(K_{3}, k_{1}|G, v) = 0, then e(G_{v}) = e(G) − d^{2}(v) (since then d^{2}(v) counts each edge in E \ E_{v} exactly once). Generalising, we get

Lemma 2.5. If G = (V, E) is a triangle free graph, and S = {v_{1}, …, v_{r}} ⊆ V an independent set, then

n(G) − n(G_{v_{1},...,v_{r}}) = |B(S; 1)| = r + ∑_{i=1}^{r} d_{G_{v_{1},...,v_{i−1}}}(v_{i}) , and

e(G) − e(G_{v_{1},...,v_{r}}) = d(B(S; 1)) − |E|_{B(S;1)} = ∑_{i=1}^{r} d_{G_{v_{1},...,v_{i−1}}}^{2}(v_{i}) .  □

Lemma 2.6. Let G be an edge critical and connected triangle free graph, and let v ∈ V (G). (a) If v is bivalent, then comp(G_{v}) = 1.

(b) If v is trivalent, G_{v} = G′ + G′′, G′ ≠ ∅ ≠ G′′, G′ is strongly s′-stable, and G′′ is strongly s′′-stable, then

d^{2}(v) ⩾ s′ + s′′ + 6 .

Proof. First, note that

α(G_{v}) = α(G) − 1 ⩾ d(v) − 1 ⩾ 1 ⟹ G_{v} ≠ ∅,

by lemma 2.4. Thus, in case (a), for a contradiction, we also may assume G_{v} = G′ + G′′ with both G^{(ν)} non-empty.

In both cases, let lk v = {w_{1}, …, w_{d(v)}}, X_{i} = lk(w_{i}) \ {v} (for i = 1, …, d(v)), X = ⋃_{i=1}^{d(v)} X_{i}, X^{(ν)} = X ∩ V (G^{(ν)}) = B(v; 2) \ B(v; 1) (for ν = 1, 2), and X_{i}^{(ν)} = X_{i} ∩ V (G^{(ν)}). By connectedness, both E_{lk(v),X^{(ν)}} must be non-empty.

Now, in case (a), if X′ did not destabilise G′, then the edges in E_{lk(v),X′} were redundant, and else so were the edges in E_{lk(v),X′′}, in either case contradicting the edge criticality.

In case (b), similarly, X^{(ν)} must destabilise G^{(ν)} for both ν. By the assumptions, in particular,

(2) a^{(ν)} := |E_{X^{(ν)},lk v}| = |X_{1}^{(ν)}| + |X_{2}^{(ν)}| + |X_{3}^{(ν)}| ⩾ |X^{(ν)}| ⩾ s^{(ν)} + 1, ν = 1, 2 .

In particular, clearly d^{2}(v) = 3 + |E_{X,lk v}| = 3 + a′ + a′′ ⩾ s′ + s′′ + 5, and it suffices to prove that equality would lead to a contradiction.

Indeed, the only way to have equality would be to have equalities in (2), too, whence on the one hand all the X_{i}^{(ν)} were disjoint, while on the other hand X^{(ν)} were a minimal and non-independent destabiliser of G^{(ν)}, for both ν. In particular, for each ν, at least two of X_{1}^{(ν)}, X_{2}^{(ν)}, and X_{3}^{(ν)} were non-empty; whence, without loss of generality, we could assume X′_{3} ≠ ∅ ≠ X′′_{3}. However, then the X_{1}^{(ν)} ∪ X_{2}^{(ν)} were proper subsets of the X^{(ν)}, whence neither X_{1}^{(ν)} ∪ X_{2}^{(ν)} would destabilise G_{v}, whence nor would X_{1} ∪ X_{2}. Thus, there were an independent (k −1)-subset S of V (G_{v})\(X_{1} ∪X_{2}); but then S ∪{w_{1}, w_{2}} were an independent (k + 1)-subset of G, against the assumptions; the sought contradiction.

2.4 E-numbers.

An (i, j; n, e) realiser is a graph G with ω(G) < i, α(G) < j, n(G) = n, and e(G) = e. The e-number e(i, j; n) is the minimal number e, such that there are (i, j; n, e) realisers, or ∞, if no such realisers exist for any e. These numbers are closely related to the (classical 2-colours) Ramsey numbers; in fact, these may be defined by

R(i, j) := min {n ∈ N : e(i, j; n) = ∞} .

There has been some efforts to determine the e-numbers e(3, k + 1; n). In [2] inter alia all such e-numbers for k + 1 ⩽ 10 are listed. The non-negative linear invariants and constructions of graphs with invariant value 0 provide some infinite families of e-values; as shown in [4, theorems 1 and 4] and [5, theorem 5.1.1 and corollary 5.3.4],

Proposition 1 (Radziszowski, Kreher). For k ⩾ 4 and either 0 ⩽ n ⩽ 3.25k − 1 or n = 3.25k,

e(3, k + 1; n) = max (0, n − k, 3n − 5k, 5n − 10, 6n − 13k) .

Moreover, for all n and k, e(3, k + 1; n) ⩾ 6n − 13k. □

3 Constructing graphs step by step.

From now on, all graphs considered in this article are triangle free, unless explicitly otherwise denoted.

Graphs ‘close to a limit’ will tend to share more structure than ‘graphs in general’. Often, they also have subgraphs ‘close to’ that limit. This may make their structure tractible to recursive treatment.

Radziszowski and Kreher consider d-extensions G_{v} ⊂ G, where d(v) = d, and where G_{v} is demanded to be edge number critical with respect to n(G_{v}) and α(G_{v}). Here, we consider somewhat more general kinds of extensions, called stitches. Indeed, stress is both on the details for each such stitch (or extension), and on the way the whole graph may be composed by such steps. I found the analogy with knitting or chrochet rather apt, and therefore partly follow chochet terminology.

Formally, quite generally, a stitch is a pair (G, G′) = ((V, E), (V′, E′)) of graphs, such that G′ is the induced subgraph of G on V′ ⊂ V and M = V \V′ is a minimal destabiliser of G. The latter condition precisely means that

α(G′) + 1 = α(G′′) = α(G)

for the induced graph G′′ on any V′′ with V′ ⊂ V′′ ⊆ V. Less formally, this G may be called ‘a stitch of G′’. The stitch is classified by the corresponding minimal destabiliser M, and by the way M is ‘fastened’ at G′.

Thus, generalising the concept d-extensions from [5], a d-stitch is a graph G and a specified vertex v ∈ V (G), such that d(v) = d and α(G_{v}) = α(G) − 1, but that no edge in B(v; 1) may be removed without increasing the independence number. Note, that the last condition certainly is satisfied, if G is edge critical.

The most simple case is the 1-stitch, extending ∅ to P_{2}, the 2-vertices path.

In general, the graphs we are interested of here may be constructed from scratch by a number of d-stitches, for various d.

If H is a d-stitch of H_{v}, then call v the apex of the stitch. Moreover, the set X of vertices of distance exactly 2 from v is called the base of the stitch, which also is said to be based at X. Note, that X is a subset of V (H_{v}). If moreover the stitch is a 2-stitch, then X destabilises H_{v}, and is bipartite (since the neighbourhoods of the two neighbours of v must be an independent set).

Conversely, a bipartite minimal destabiliser M of a graph G can be used as base of a 2-stitch of G. (Note, that the ‘bipartitivity’ is self-evident, if M contains at most four vertices, since that is too few for a 5-cycle or a larger cycle of odd length.) If G is edge critical, and v ∈ V, then B(v; 1) is such a destabiliser. In this case, the corresponding 2-stitch also is said to be based at v. In these cases, the 2-stitch (which is uniquely defined up to isomorphisms) also may be denoted cr_{2}(G; M) or cr_{2}(G; v); the index 2 may be omitted. The apex of that stitch, say v′, may be used as the base of a new stitch cr(cr(G; M); v′), also denoted cr^{2}(G; M); et cetera.

We now may form the most fundamental crochet, a (simple) chain, by successively adding 2-stitches to C_{5}^{2}. Thus, put Ch_{2} := C_{5}, and Ch_{k} := cr^{k−2}(C_{5}; c_{1}) ≃ cr(Ch_{k−1}; p) for any k ⩾ 3 (and any vertex c_{1} in C_{5} or bivalent p in Ch_{k−1}, respectively).

[figure: Ch_{3}, alias C_{5} .; Its crochet pattern.; Ch_{5} as a 2-stitch of Ch_{4} .; Its crochet pattern.]

2Actually, C_{5} ≃ cr_{2}(P_{2}), and P_{2} ≃ cr_{1}(∅), whence instead indeed we might start “from scratch”, putting Ch_{1} := P_{2} and Ch_{0} := ∅; however, we have no use of this notation in this article.

the electronic journal of combinatorics 16 (2009), #R00 8

[figure: The bicycle BC_{6} .; e_{1}; e_{2}; e_{3}; e_{4}; e_{5}; e_{6}; d_{1}; d_{2}; d_{3}; d_{4}; d_{5}; d_{6}; d_{7}; d_{8}; d_{9}; d_{10}; d_{11}; d_{12}; Its crochet pattern.]

Next, we may consider 3-stitches of chains. The simplest such are the bicycles. The bicycle BC_{k} (k ⩾ 4) consists of an (induced) outer cycle {d_{1}, …, d_{2k}} ≃ C_{2k} and an (induced) inner cycle {e_{1}, …, e_{k}} ≃ C_{k}, with the connecting edges {d_{2i−2,e_{i}}} and {d_{2i+1}, e_{i}} for i = 1, …, k (where as usual the outer and inner cycle vertex indices may be calculated modulo 2k and modulo k, respectively).

Indeed, for any trivalent v in BC_{k}, (BC_{k})_{v} ≃ Ch_{k−1}.

The bicycles may be considered as crochet loops. They are rather symmetric, and like the chains well-defined up to isomorphism, by means of the single parameter k = α(BC_{k}). However, the next class we consider are ‘loop-chains’, where we add a succession of 2stitches to a bicycle, to get a pending attached chain; and here we need three parameters: The length of the loop, the length of the chain, and a description of how the chain is attached to the loop.^{3} Here, we only are interested in attachments at destabilisers of minimal size; i. e., a loop-chain may be written as cr^{k−l}(BC_{l}; M), where l ⩾ 4, k − l ⩾ 1, and M is a BC_{l} destabiliser of size four. As we shall see in lemma 5.2, there are up to isomorphism just three possible M, isomorphic to K_{1,3}, P_{4}, or C_{4}, respectively, whence we may let the third parameter range over just the set {K_{1,3}, P_{4}, C_{4}}.

[figure: The loop-chain cr^{2}(BC_{4}; P_{4}).; Its crochet pattern.; The loop-chain cr^{3}(BC_{4}; K_{1,3}).; Its crochet pattern.]

3In the crochet pattern, the attachment is represented by a trivalent, while the mood of attachment conveniently may be represented by associating outgoing directions to some of the edges at that trivalent.

the electronic journal of combinatorics 16 (2009), #R00 9

[figure: The loop-chain cr(BC_{6}; C_{4}).; Its crochet pattern.]

Finally, we consider one famous “cyclic graph”, the unique triangle free graph on 13 vertices with independence number 4. The graph often is called H_{13}; here, I use the more descriptive notation W_{13;1,5}, signifying that it has 13 indexed vertices, and that each vertex is connected to those with a difference 1 or 5 in indices (again calculated modularly, where appropriate)^{4}. By the definitions and inspection, W_{13;1,5} is a 4-stitch of Ch_{3}, where any vertex in W_{13;1,5} may be chosen as the apex.

4 The main result.

Recall that q(G) = e(G) − 5n(G) + 10 α(G) and t(G) = e(G) − 6n(G) + 13 α(G). The following is a summary of results by Radziszowski and Kreher, collected from [5]:

Proposition 2 (Radziszowski, Kreher). For any triangle free graph G, q(G) ⩾ 0 and t(G) ⩾ 0. Moreover, q(G) = 0 if and only if G is a sum of chains and bicycles. If G is a sum of bicycles and copies of W_{13;1,5}, then t(G) = 0; and as a partial converse, if α(G) ⩽ 6 and t(G) = 0, then indeed G is such a sum. Finally, in any case, if t(G) = 0 but G ≠ ∅, then 3 ⩽ δ(G), but G is not 3-regular.

The q inequality and extremal graph characterisation is proposition 2.2 (b) and theorem 4.3.1 in [5], respectively. The t inequality is their (main) theorem 5.1.1, the equality cases is proposition 6.3 (e), and the α(G) ⩽ 6 graphs characterisation is a remark at the beginning of the proof of lemma 5.1.5, in p. 77. That δ(G) ⩾ 3 is contained in lemma 5.1.5. The last statement, that G cannot be non-empty but 3-regular, is implicitly noted en passant in the proof of lemma 5.1.6, since such a G would be a “minimum graph with average degree not exceeding 10/3”, in the terminology of that proof.

4Another, more algebraic way to define W_{13;1,5} is by taking the Galois field GF (13) as its vertex set, and putting E(W_{13;1,5}) := {{x, y} ⊂ GF (13) : (x − y)^{4} = 1}.

the electronic journal of combinatorics 16 (2009), #R00 10

They suggest that t(G) = 0 only for sums of bicycles and W_{13;1,5} copies. This indeed is true, but for my proof to work, I also had to characterise some triangle free graphs with t(G) = 1:

Theorem 3. Let G be any triangle free graph.

(a) If t(G) = 0, then each component of G is a bicycle or isomorphic to W_{13;1,5}.

(b) If t(G) = 1 and δ(G) ⩽ 2, then one component of G is a chain or a loop-chain, and any other components are bicycles and copies of W_{13;1,5}.

Put

Ψ = {G : ω(G) < 3 ∧ t(G) = 0},
Ψ′ = {G : ω(G) < 3 ∧ t(G) = 1 ∧ δ(G) ⩽ 2},
Γ = {G : each component of G is a bicycle or a W_{13;1,5} copy}, and
Γ′ = ({chains of lengths ⩾ 2} ∪ {loop-chains}) + Γ,

with the usual algebraic interpretation of a sum of sets of addable elements. The theorem now may be reformulated as

(3)  Ψ = Γ and Ψ′ = Γ′.

By just calculating t(G) and δ(G) for the connected members of Ψ ∪ Ψ′ and employing linearity, it is easy to see that indeed Γ ⊆ Ψ (as noted in proposition 2), and that Γ′ ⊆ Ψ′. Thus, we only have to prove the converse inclusions in (3).

Since t is linear, and is non-negative on triangle free graphs, the class Ψ is closed under addition; in fact, a graph G belongs to Ψ if and only if every component of G does. On the other hand, Ψ′ obviously is not closed under addition. Instead, every graph in Ψ′ has exactly one component C with t(C) = 1, while the other components belong to Ψ. Moreover, since every one of the latter components has minimal valency ⩾ 3 by proposition 2, but G does not, in fact C ∈ Ψ′. In other words,

(4)  Ψ′ = {G ∈ Ψ′ : comp(G) = 1} + Ψ.

Thus, while Ψ ∪ Ψ′ is not closed under addition, it is closed under taking components or other summands:

(5)  G′ + G′′ ∈ Ψ ∪ Ψ′ ⟹ G′, G′′ ∈ Ψ ∪ Ψ′ .

Thus, in order to prove the theorem, it is sufficient to prove that a connected G in Ψ (Ψ′) also must belong to Γ (Γ′, respectively), by means of induction with respect to α(G). This will be done in section 6.

As a direct consequence of the theorem, and since there are realisers for (3, 6; 16, 32), (3, 7; 19, 37) and (3, 8; 22, 42) and by linearity, we get a slight improvement of proposition 1:

Corollary 4. Let n and k ⩾ 5 be integers. If 3.25k −1 < n < 3.25k, then e(3, k + 1; n) = 6n − 13k + 1, and if n > 3.25k, then e(3, k + 1; n) ⩾ 6n − 13k + 1. □

5 Preparatory results.

I’ll start by collecting the further needed results in a few lemmata. As far as possible, I refer their proofs to corresponding [5] results.

Lemma 5.1. For any k ⩾ 2, α(Ch_{k}) = k, and Ch_{k} is 2-stable and has no destabilising subset of size 3 other than B(v; 1) for any bivalent v therein.

Proof. This is essentially a reformulation of [5, lemma 4.2.2 (a)].

Lemma 5.2. For any k ⩾ 4, α(BC_{k}) = k, and BC_{k} is 3-stable and only has three kinds of destabilising 4-sets of vertices, namely (1): A ball B(d_{i}; 1), i. e., a trivalent, together with its three neighbours; (2): an induced path {d_{2d−1}, d_{2d}, d_{2d+1}, d_{2d+2}}; or (3): an induced 4-cycle {d_{2d}, d_{2d+l}, e_{d}, e_{d+1}}. (Here, outer and inner wheel indices may be counted modulo 2k and k, respectively.)

Proof. The 3-stability essentially is a reformulation of [5, lemma 4.2.1], and the independence number is implicitly determined by [5, lemma 4.2.2 (b)].

For the proof of the rest, let M be a destabiliser of size 4 in BC_{k}. Since BC_{k} is connected and contains at least eight trivalents, at least one of them, say v, is a neighbour of M (but not contained in M). Now, BC_{k} is a 3-stitch of Ch_{k−1} with apex v, as depicted in figure IV, p. 72, in [5]. Moreover, on the one hand, there is some x ∈ M ∩ lk v, while on the other hand M′ := M ∩ V (Ch_{k−1}) destabilises Ch_{k−1}. (Else, there were an independent (k − 1)-subset S of V (Ch_{k−1}) \ M, whence S ∪ {v} were an independent k-subset of V (BC_{k}) \ M; but M destabilises BC_{k}.)

Thus and by lemma 5.1, M′ consists of one of the four bivalents in Ch_{k−1}, together with its two neighbours in Ch_{k−1}, while x is one of the three neighbours of v. This leaves just twelve potential M to investigate, and it it easy to see that most of them are not destabilisers of BC_{k}. The lemma follows.

The next result should be rather well-known.

Lemma 5.3. W_{13;1,5} is 4-stable.

Proof. If M ⊂ V (W_{13;1,5}) and has at most four vertices, then the induced graph on V (W_{13;1,5})\M has at least 9 = R(3, 4) vertices, whence M does not destabilise W_{13;1,5}.

Lemma 5.4. There is a 4-cycle through each vertex of degree at least three in the BC_{k} (k ⩾ 4), W_{13;1,5}, and the Ch_{k} (k ⩾ 2) and other graphs in Γ∪Γ′. In particular, any graph in Γ ∪ Γ′ contains a 4-cycle, except ∅ ∈ Γ and C_{5} ∈ Γ′.

Proof. Inspection of the enumerated graphs.

6 The proof of the theorem.

As remarked in section 4, it is sufficient to prove the following for each k, by means of induction with respect to k:

(6)  If comp(G) = 1, α(G) = k, ν ∈ {0, 1}, and G ∈ Ψ^{(ν)}, then G ∈ Γ^{(ν)}.

Thus, for the whole proof, fix a positive integer k_{0}, and assume that (6) holds for each k < k_{0}, that G = (V, E) ∈ Ψ ∪ Ψ′, and that k = k_{0} = α(G). Moreover, let n = n(G), e = e(G), t = t(G) ∈ {0, 1}, and δ = δ(G) (where δ ⩽ 2 if t = 1), and let v be a vertex with maximal second valency among the vertices with minimal valency in G. In other words, we assume that

(7)  d(v) = δ ∧ (d(w) = δ ⟹ d^{2}(w) ⩽ d^{2}(v)) .

Finally, let the neighbours of v be w_{1}, …, w_{d(v)}, where we may assume

(8)  d(v) ⩽ d(w_{1}) ⩽ … ⩽ d(w_{d(v)}),

and for i = 1, …, δ, let X_{i} = lk(w_{i}) ∩ V (G_{v}), and let X = ⋃_{i=1}^{δ} X_{i} = B(v; 2) \ B(v; 1).

If there were a redundant ε ∈ E, then (t = 0 ⟹ t(V, E \ {ε}) = −1), and (t = 1 ∧ δ ⩽ 2 ⟹ t(V, E \ {ε}) = 0 ∧ δ(V, E \ {ε}) ⩽ δ ⩽ 2), in either case contradicting proposition 2. Thus, instead,

(9)  G is edge critical.

In particular, lemma 2.4 applies, whence

α(G_{v}) = k_{0} − 1 .

Thus and by (7), in particular, on the one hand d^{2}(v) ⩾ δ^{2}, while on the other hand

0 ⩽ t(G_{v}) = (e − d^{2}(v)) − 6(n − δ − 1) + 13(k_{0} − 1) = t + 6δ − 7 − d^{2}(v) .

Summing up, we have the useful restrictions

(10)  δ^{2} ⩽ d^{2}(v) ⩽ t + 6δ − 7 ⩽ 6δ − 6 .

We start by considering a G ∈ Ψ′. Note that then δ = 2, since a lower value would contradict (10). For the same reason,

4 ⩽ d^{2}(v) ⩽ 6 .

We thus may make a case division with respect to the value of d^{2}(v). However, first note that for either value

(11)  comp(G_{v}) = 1

by (9) and lemma 2.6.

\underline{d^{2}(v) = 2 + 2 = 4}: By (10) and (7) both d(w_{i}) = 2 and both d^{2}(w_{i}) = 4, too. In other words, each bivalent only has bivalent neighbours, whence the connected graph G must be 2-regular. Thus, G = C_{l} for some l ⩾ 4. In fact, we must have l = 5, by the arguments in the proof of [4, lemma 2 (a)] (or by directly calculating the t(C_{l}) for all l). Thus, indeed, G ≃ C_{5} = Ch_{2} ∈ Γ′.

\underline{d^{2}(v) = 2 + 3 = 5}: By (8), then d(w_{1}) = 2 and d(w_{2}) = 3. Moreover, t(G_{v}) = 1, too, whence (6) applies inductively for G_{v}. In particular, thus δ(G_{v}) ⩾ 2. Hence, if x is the single neighbour of w_{1} in G_{v}, then

d(x) ⩾ 1 + d_{G_{v}}(x) ⩾ 1 + 2 = 3 ∧ d^{2}(w_{1}) = d(v) + d(x) ⩾ 2 + 3 = 5 .

On the other hand, d^{2}(w_{1}) ⩽ d^{2}(v) = 5 by the assumption (7). We thus must have equalities.

In particular, x is a bivalent in G_{v}, which thus belongs to Ψ′, and thus by (6) to Γ′. Thus and by (11), up to isomorphisms, either G_{v} = Ch_{k_{0}−1}, or

G_{v} = cr^{i+1}(BC_{k_{0}−2−i}; M)

for some i ⩾ 0 and a destabilising 4-subset M ⊂ V (BC_{k−2−i}) of one of the three kinds enumerated in lemma 5.2. In either case, it is sufficient to prove that G is a 2-stitch with apex v and based at x and its two neighbours in G_{v}. In other words, we want to show that

X = B(G_{v}, x; 1),

or, equivalently, that

X_{2} = lk_{G_{v}}(x).

Now, X is a destabilising subset of G_{v} of size ⩽ 3, since the induced graph on V (G_{v})\X is G_{w_{1},w_{2}} and

α(G_{w_{1},w_{2}}) ⩽ k_{0} − 2 < α(G_{v})

by lemma 2.3. Moreover, since G is triangle free, X_{2} is an independent 2-set in G_{v}. Thus, we have a trichotomy: Either |X| = 2, or |X| = 3 ∧ comp(X) ⩾ 2, or indeed X = B(G_{v}, x; 1); we have to prove that the first two alternatives are impossible.

For G_{v} = Ch_{k−1}, the destabilisers of size ⩽ 3 are characterised in lemma 5.1, and they indeed must be of size 3 and connected. Thus, assume instead that G_{v} = cr^{i+1}(BC_{k−2−i}; M), and, for a contradiction, that either X = X_{2} is an independent 2-set, or |X| = 3 but |E_{X}| ⩽ 1.

Since α(G_{w_{1},w_{2}}) ⩽ k_{0} − 2 (and by proposition 2),

\begin{matrix}0 ⩽ t(G_{w_{1},w_{2}}) ⩽ t(G_{v}) − (∑_{y∈X} d_{G_{v}}(y) − |E_{X}|) + 6 |X| − 13 \\ = 6(|X| − 2) + |E_{X}| − ∑_{y∈X} d_{G_{v}}(y). \end{matrix}

Since moreover δ(G_{v}) = 2, and G_{v} (and thus X) contains at most two bivalents, |X| = 2 would yield a glaring contradiction, and |X| = 3 but X disconnected only could be possible if in addition |E_{X}| = 1 and X consists of two bivalents and one trivalent in G_{v}; and, moreover, then t(G_{w_{1},w_{2}}) = 0, whence G_{w_{1},w_{2}} ∈ Γ by (6)..

However, then the single edge in X must be the edge between the two bivalents. Thus, if y is the trivalent in X, then all its three G_{v} neighbours (say z_{1}, z_{2}, and z_{3}) belong to V (G_{w_{1},w_{2}}). Thus, either some z_{i} were trivalent in G_{v}, and therefore of valency less than 3 in G_{w_{1},w_{2}}, contradicting δ(G_{w_{1},w_{2}}) ⩾ 3 (by proposition 2); or

d_{G_{v}}^{2}(y) = ∑_{i} d_{G_{v}}(z_{i}) ⩾ 3 · 4 = 12 ⟹ t(G_{v,y}) ⩽ 0,

but since d_{G_{v,y}}(x) ⩽ 2 < 3, again we would have a contradiction to the proposition.

Thus, indeed we have eliminated all possibilities, with the exception X = B(G_{v}, x; 1), whence indeed G = cr(G_{v}; x) ∈ Γ′.

\underline{d^{2}(v) = 6}: Then t(G_{v}) = 0, but G_{v} is destabilised by X. By (11), (6), and lemmata 5.3 and 5.2, thus indeed G_{v} = BC_{k_{0}−1} and G = cr(BC_{k_{0}−1}; X), with X being of one of the three kinds given in lemma 5.2. Thus, indeed, then G ∈ Γ′.

Thus, we have proved (6) for G ∈ Ψ′ (and k = k_{0}). In particular, if there is a counterexample to (6) with a minimal value k = k_{0} for its independence number, then G ∈ Ψ \ Γ, whence in particular

k_{0} ⩾ 7

by proposition 2. In the rest of the proof, for a contradiction, we indeed assume that G is such a minimal counterexample.

Since t = 0, and by proposition 2, and summing up, we may strengthen (10) somewhat: In the sequel we may assume that

t = 0 ∧ k_{0} ⩾ 7 ∧ 3 ⩽ δ ⩽ 4 ∧ δ^{2} ⩽ d^{2}(v) ⩽ 6δ − 7 .

This leaves five cases to consider, with δ = 3 and d^{2}(v) ∈ {9, 10, 11}, and with δ = 4 and d^{2}(v) ∈ {16, 17}. Again, we mainly consider them separately. We start with the δ = 3 cases.

\underline{d^{2}(v) = 9}: As in the d^{2}(v) = δ^{2} = 4 case, this would force G to be regular; this time, 3-regular, contradicting proposition 2.

Temporarily suspending the case division analysis, note that in the remaining two δ = 3 cases,

(12)  0 ⩽ t(G_{v}) = t − d^{2}(v) + 6(d(v) + 1) − 13 = 11 − d^{2}(v) ⩽ 1 .

Furthermore, if in addition G_{v} = G′ + G′′ with the G^{(ν)} non-empty, then without loss of generality we could assume t(G′) = 0 ⩽ t(G′′) ⩽ 11 − d^{2}(v) ⩽ 1.

However, if then moreover d^{2}(v) = 11, then both G^{(ν)} were contained in Γ by (6), and thus were strongly 3-stable, by lemmata 5.2 and 5.3 for their components. Thus and by lemma 2.6 (b), then 11 = d^{2}(v) ⩾ 3 + 3 + 6 = 12, a contradiction.

Likewise, if then instead moreover d^{2}(v) = 10, then necessarily δ(G′′) = δ(G_{v}) ⩽ 2, as we shall see in a moment (and since δ(G′) ⩾ 3 by proposition 2), whence then G′ were strongly 3-stable, and G′′ would belong to Γ′ and thus be strongly 2-stable, by also employing lemma 5.1 for one G′′ component; this time yielding the contradiction 10 ⩾ 3 + 2 + 6 = 11.

Thus, instead, in the remaining δ = 3 cases, we again have

(13)  comp(G_{v}) = 1 .

\underline{d^{2}(v) = 3 + 3 + 4 = 10}: By (8) and (7), then d(w_{1}) = d(w_{2}) = 3 d(w_{3}) = 4, and moreover d^{2}(w_{1}) ⩽ 10 ⩾ d^{2}(w_{2}), too. Thus, X_{1} and X_{2} contain trivalents, whence indeed δ(G_{v}) ⩽ 2. Thus and by (12), (13), and inductively by (6), then G_{v} ∈ Γ′ (and in fact G_{v} contains at least two bivalents), and more precisely G_{v} = Ch_{k_{0}−1}, or G_{v} = cr^{i+1}(BC_{j}; M) where M ∈ {K_{1,3}, P_{4}, C_{4}} were a destabiliser of BC_{j}, and j = k_{0} − (i + 2) ⩾ 5 − i.

However, the latter possibility may be discarded: If so, then no trivalent in G_{v} could remain a trivalent in G, since then some such remaining trivalent x would have d^{2}(x) > 10; but there were at least 2j − 4 + 2i ⩾ 6 trivalents in G_{v}; but X would not contain more than seven elements, including the two bivalents of G_{v}, whence some G_{v} trivalent indeed would be outside X and thus remain trivalent in G.

Thus, instead, G = Ch_{k_{0}−1}. Hence, [5, lemma 4.2.2] yields that G ≃ BC_{k} ∈ Γ, against the assumption that it were a minimal counterexample.

\underline{d^{2}(v) = 11}: Since t(G_{v}) = 0 and by (6) and (13), and since k_{0} ⩾ 7 > 5,

G_{v} ∈ Γ ∧ G_{v} ≄ W_{13;1,5} ⟹ G_{v} = BC_{k_{0}−1} .

Next, note that the cardinality of X is at most 8, and that equality holds if and only if the X_{i} are disjoint, i.e., if and only if N(C_{4}|G, v) = 0. Moreover, any w_{i} of degree 3 has d^{2}(w_{i}) ⩾ 3 + 4 + 4 = 11, whence we have equality by (7), and thus then

t(G_{w_{i}}) = 0 ⟹ G_{w_{i}} ∈ Γ ⟹ δ(G_{w_{i}}) ⩾ 3;

whence there cannot be more than one trivalent w_{i}. Thus and by (8), and analogously,

d(w_{1}) = 3 ∧ d(w_{2}) = d(w_{3}) = 4 ∧ (x ∈ X_{1} ⟹ d(x) = 4).

Next, the number of trivalents in G_{v} = BC_{k_{0}−1} is 2(k_{0} − 1) ⩾ 12. Thus, some of the G_{v} trivalents are adjacent to X but not contained therein. Each such trivalent y must have d^{2}(y) = 3 + 4 + 4 in G; and they appear in pairs. Reciprocially, for any such y, G_{y} ≃ BC_{k−1}, too, and v ∈ V_{y}. Thus and by lemma5.4,

N(C_{4}|G, v) ⩾ N(C_{4}|G_{y}, v) ⩾ 1;

whence X has at most 7 vertices; whence there are at least k_{0} −4 pairs of trivalents in G_{v}, which remain trivalent in G. However, some of these pairs would have to be ‘too close’ in G_{v}, yielding a trivalent y with t(G_{y}) = 0 but δ(G_{y}) < 3, a contradiction.

Thus, instead, d(v) = δ = 4, and 16 ⩽ d^{2}(v) ⩽ 17. We treat the higher value first, since it can be done briefly.

\underline{d^{2}(v) = 4 + 4 + 4 + 5 = 17}: By (8), d(w_{1}) = d(w_{2}) = d(w_{3}) = 4, but d(w_{4}) = 5. Moreover, since t(G_{w_{4}}) ⩾ 0 by proposition 2, d^{2}(w_{4}) ⩽ 23. However, then X_{4} must contain a tetravalent, say u; and necessarily d^{2}(u) = 4 + 4 + 4 + 5 = 17, too. This would make t(G_{u}) = 0 and v an element of V (G_{u}), whence by the inductive assumptions and lemma 5.4, there were a 4-cycle going through v and two of its neighbours of degree 4, say w_{1} and w_{2}.

If x were the last vertex of that 4-cycle, we would be in a dilemma, as regards the degree of x. Either, x were tetravalent, and therefore of degree at most 2 in G_{v}; or it were pentavalent, whence d^{2}(w_{1}) = 17 and t(G_{w_{1}}) = 0, but w_{2} were of degree at most 2 in G_{w_{1}}. In either case, we would get a contradiction to proposition 2.

\underline{d^{2}(v) = δ^{2} = 16}: In analogy with the other d^{2}(v) = δ^{2} cases, G is 4-regular. Moreover, for each vertex x, t(G_{x}) = 1, whence and inductively by (6) either δ(G_{x}) > 2 or G_{x} ∈ Ψ′ ⟹ G_{x} ∈ Γ′ ⟹ δ(G_{x}) = 2. In other words, anyhow,

(14)  δ(G_{x}) ⩾ 2, and #3(G_{x}) + 2#2(G_{x}) = d^{2}(x) − d(x) = 12 .

It remains to show that indeed G ≃ W_{13;1,5}. Now, if in addition there is a 4-cycle in G, going through v, say, then this is relatively easy to show. As we just saw, then G_{v} ∈ Ψ′ and δ(G_{v}) = 2. Moreover, we in addition may assume v to be chosen in such a manner that the independence number of the induced graph on the set of G_{v} bivalents is as large as possible.

Now, since G is connected and 4-regular, G_{v} has no 4-regular component. However, for each not 4-regular connected graph H in Γ ∪ Γ′, #3(H) + 2#2(H) ⩾ 8. Thus, and by (14) and linearity,

12 = #3(G_{v}) + 2#2(G_{v}) ⩾ 8 comp(G) ;

whence G_{v} must be connected, and in fact, without loss of generality, either G_{v} = Ch_{3}, or G_{v} = cr^{i}(BC_{7−i}; {d_{3}, d_{4}, d_{5}, d_{6}}) for some i ∈ {1, 2, 3}.

However, in the latter case, G_{d_{4}} would contain an independent 2-set of bivalents, consisting of e_{2} and of one of the vertices added to BC_{7−i} in the first stitch of the chain, but G_{v} would contain no such independent 2-set, in contradiction to the choice of v.

Thus, instead, in fact G_{v} ≃ Ch_{3}, from where it is easy to deduce by inspection that indeed G ≃ W_{13;1,5}.

Thus, only the seemingly hardest case remains, that G would be both connected, 4regular, and square free. Actually, in [5], the same kinds of potential counterexamples, but to the statement (1), also gave rise to considerable work; Radziszowsky and Kreher use nine pages just to eliminate this case^{5}, consisting of their section 5.2, and of section 5.3 to the end of the proof of their main theorem. Happily enough, most of their proof also works in our situation, with the help of a few observations.

5In [1], the elimination is referred to a slightly more general result, whose proof is even longer.

the electronic journal of combinatorics 16 (2009), #R00 17

To be more precise, Radziszowski and Kreher prove (1) by induction, assuming that indeed t(H) ⩾ 0 for any triangle free H with α(H) < k_{0}, and then consider a potential counterexample

G ∈ Λ := {G : ω(G) ⩽ 2 ∧ α(G) = k_{0} ∧ t(G) < 0}.

They reasonably fast prove that then G must be connected and 4-regular, and must have girth(G) ⩾ 5 ([5, lemma 5.1.6 and proposition 5.1.8]). They then eventually prove that the existence of such a G yields a contradiction. The short story is that the proof of the latter mutatis mutandis may be applied for our G ∈ Γ. Granting this, the induction step and thus our main theorem is proved.

The somewhat longer story is that some care should be taken with the “things to be changed”. I therefore provide a ‘translation’ of their sequence of lemmata to our situation, with the emphasis on the changes, and omitting all parts of the proofs which indeed are unchanged. In particular, I introduce a shortcut, simplifying the treatment of 6-cycles. My intention is that my summary should be intelligible in itself; however, a comprehensive understanding of the full proof probably is hard without accessing [5] directly.

In fact, while the [5] arguments repeatedly employ that their G has t(G) = −1, this is mainly used indirectly. They prove, that n(G) must be fairly large ([5, proposition 5.1.7]), and that thus certain subgraphs of the form G_{v_{1},...,v_{r}} both must be non-empty and have the t(G_{v_{1},...,v_{r}}) ⩾ t(G) + 1, with δ(G_{v_{1},...,v_{r}}) ⩾ 3 in case of equality. Moreover, in all the applications, they a fortiori are able to exclude α(G_{v_{1},...,v_{r}}) strictly less than the bound given by lemma 2.3. We start by proving three statements substituting for this, and then show how to use them in order to modify the lemma proofs in [5].

Thus, again, let G ∈ Γ be an assumed minimal counterexample to theorem 3, with α(G) = k_{0}, n(G) = n, and e(G) = e, and recall that then G is 4-regular and connected, and has N(C_{4}|G) = N(K_{3}|G) = 0, i. e., has girth(()G) ⩾ 5. In particular, e−6n+13k_{0} = t = t(G) = 0 and e = 2n, whence 4n = 13k_{0}, and k_{0} is divisible by 4. Since moreover k_{0} ⩾ 7 by proposition 2, we actually must have k_{0} ⩾ 8, and thus get

(15)  n ⩾ 26,

which should replace the calls to [5, lemma 5.1.7] in Radzisowski’s and Kreher’s proofs.

For any non-empty independent set S = {v_{1}, …, v_{r}} in G, α(G_{v_{1},...,v_{r}}) ⩽ k_{0} − r < k_{0} by lemma 2.3, whence the inductive assumptions yield that G_{v_{1},...,v_{r}} ∈ Γ if t(G_{v_{1},...,v_{r}}) ⩽ 0, and G_{v_{1},...,v_{r}} ∈ Γ′ if t(G_{v_{1},...,v_{r}}) = 1 and δ(G_{v_{1},...,v_{r}}) ⩽ 2. However, since G contains no 4-cycle, neither does G_{v_{1},...,v_{r}} whence (G_{v_{1},...,v_{r}} ∈ Γ ⟹ G_{v_{1},...,v_{r}} = ∅), and likewise (G_{v_{1},...,v_{r}} ∈ Γ′ ⟹ G_{v_{1},...,v_{r}} ≃ C_{5}). Together with (15), this yields that for such an S

(16)  t(G_{v_{1},...,v_{r}}) ⩾ 1 if |B(S; 1)| < 26,

and

(17)  t(G_{v_{1},...,v_{r}}) ⩾ 2 if |B(S; 1)| < 21 and δ(G_{v_{1},...,v_{r}}) ⩽ 2 .

On the other hand, since t(G) = t = 0 and by lemmata 2.5 and 2.3,

\begin{aligned}t(G_{v_{1},...,v_{r}}) & = & e(G_{v_{1},...,v_{r}}) − e − 6(n(_{v_{1},...,v_{r}}) − n) + 13(α(G_{v_{1},...,v_{r}}) − k_{0}) \\ & ⩽ & 6 |B(S; 1)| − d(B(S; 1)) − 13r + |E_{B(S;1)}|; \end{aligned}

and indeed the main application of (16) and (17) is to provide lower bounds for |E_{B(S;1)}| (which Radziszowsky and Kreher call the number of edges in the support of S). Calls to (16) and to (17) should replace calls to [5, formula (4)] and to [5, lemma 5.1.5], respectively.

We now list the sequence of properties for G, which leads to a contradiction. In most of them, Radziszowski and Kreher consider a fixed vertex v, let H = G_{v}, and let J be the induced graph on the set of trivalents in H.^{6} Thus, V (J) = X, and by (14), n(J) = 12. Most of the properties concern the graph structure of J. Let C be an arbitrary component of J.

[5, Lemma 5.2.2 (a) and (b)] state that for any path (v, t, u) of length 2 in G,

(18)  N(C_{5}, c_{1}, c_{2}, c_{3}|G, v, t, u) ⩾ 1 and N(C_{5}, c_{1}, c_{2}|G, v, t) ⩾ 3 .

The first claim is proved by noting that |E_{B({v,u};1)}| ⩾ 9 by applying [5, formula (4)] to G_{v,u}; replace this by applying (16).

[5, Lemma 5.2.3] states

girth(J) > 5, δ(J) > 1, (s ∈ C ∧ d_{J}(s) = 1 ⟹ C ≃ P_{2}), C ≃ P_{2} ∨ δ(C) ⩾ 2 .

The only modification to be made of the proof concerns the reason for the following fact (which we shall reuse later):

(19)  If s ∈ V (J) and d_{J}(s) = 1, then δ(H_{s}) = δ(G_{v,s}) ⩾ 3;

apply (17) for S = {v, s}.

[5, Lemma 5.2.4] states

N(C_{6}|J) = 0;

if (a, b, c, d, e, f) were a 6-cycle in J, then apply (16) for S = {v, a, c, e}.

[5, Lemma 5.2.5] is somewhat technical; it states that if t ∈ V (J), x, y ∈ lk_{J}(t), and d_{J}(x) = d_{J}(y) = 2, whence without loss of generality lk_{J}(x) = {t, x_{1}, x_{2}} and lk_{J}(y) = {t, y_{1}, y_{2}} with x_{2}, y_{2} ∈ V (H) \ V (J), then

x_{1}y_{2}, y_{1}x_{2} ∈ E .

The proof goes through without changes, as does the proof of [5, lemma 5.2.6], stating

d_{J}(x) = 3 ⟹ d_{J}^{2}(x) = 2 + 2 + 3 = 7 .

6Radziszowski and Kreher in parts of their proofs change meanings of n and e; however, here we retain n = n(G) and e = e(G) consistently.

the electronic journal of combinatorics 16 (2009), #R00 19

These properties suffice to limit the possible C to P_{2}, C_{8}, C_{10}, C_{12}, S_{1}, and S_{2} ([5, proposition 5.2.7]), where

S_{1} := (V (C_{12}), E(C_{12}) ∪ {c_{6}c_{12}}) and S_{2} := (V (C_{12}), E(C_{12}) ∪ {c_{6}c_{12}, c_{3}, c_{9}}).

In the next two lemmata, all of these except P_{2} are discarded. The elimination of C_{8} and C_{10} goes through unmodified; for C = J ∈ {C_{12}, S_{2}}, Radziszowsky and Kreher prove that n ⩽ 20, which here contradicts (15); and for C = J = S_{1}, (16) should be applied for S = {v, c_{1}, c_{3}, c_{5}, c_{7}, c_{9}, c_{11}}, yielding far too many edges in B(S; 1).

Thus, we know that (for any v)

(20)  J ≃ 6P_{2};

and in particular may deduce a sharper variant of (18) ([5, corollary 5.2.10 (a) and (b)]): With (v, t, u) as before,

(21)  N(C_{5}, c_{1}, c_{2}, c_{3}|G, v, t, u) = 1 and N(C_{5}, c_{1}, c_{2}|G, v, t) = 3 ;

and immediately may deduce ([5, corollary 5.2.11 (a)]

(22)  two 5-cycles can share at most one edge.

Radziszowsky and Kreher now proceed to investigate 6-cycles in G in some detail. However, actually, (19) and (20) suffice to eliminate any such 6-cycle immediately: If instead C_{6} were a subgraph of G, then choosing v := c_{1} and s := c_{3}, we would have s ∈ J, hence d_{J}(s) = 1 by (20), and hence δ(G_{v,s}) ⩾ 3 by (19); but d_{G_{c_{1},c_{3}}}(c_{5}) ⩽ 2, a contradiction. Thus, indeed we have

(23)  N(C_{6}|G) = 0 .

Thus, in order to achieve the final contradiction, it is enough to prove that G also must contain 6-cycles. Actually, in [5, lemma 5.3.2], Radziszowsky and Kreher proves that there would be at least six 6-cycles through each edge uv in their G. They start by considering two 5-cycles (u, v, x_{1}, ·, x_{3}) and (u, v, x_{2}, ·, x_{4}) through uv (existing by (21), and sharing no vertices outside uv by (22)), and then consider the independent set S = {x_{1}, x_{2}, x_{3}, x_{4}}. Following their proof, but applying (15) instead of [5, proposition 5.1.7] for S, we find that also in our situation

|E_{B(S;1)}| ⩾ 21 > 19,

indeed forcing the existence of 6-cycles, and thus the sought contradiction to (23).

To sum up, we thus have proved, that if the claims of theorem 4 hold for all triangle free graphs G with α(G) < k_{0}, then they hold for those with α(G) = k_{0}, too; whence indeed (3), and thus the theorem, follows by induction. □

7 Graphs G with vertex numbers beyond α(G).

Finally, let us briefly discuss some possible generalisations of [5, theorem 5.1.1] and of theorem 3. In this survey section, some proofs are omitted or just outlined; among these those concerning the precise definition of graphs who have crochet patterns with maximal valency at most three. (However, all the local interpretations of their patterns actually needed are presented in section 3, although in a somewhat implicit manner.)

For instance, it turns out, that a triangle free, connected, and edge critical graph G with t(G) = 1 either has δ(G) = 2 (and thus belongs to Γ′), or has a crochet pattern P with δ(P) ⩾ 2 and cycle space of dimension 2, or is one of the two 4-regular (3, 6; 16, 32) realisers. (In particular, hence, the last inequality in corollary 4 actually is strict.) On the other hand, for t(G) = 2, there are graphs (including some (3, 9; 26, 52) realising ones), which I do not know how to classify.

As we noted in section 1, (1) is just one in a sequence of linear inequalities for triangle free graphs, and the graphs with equalities in any one of them are edge number critical. Conversely, in the interval where equality may be attained in one of the inequalities without violating the others, all edge numbers critical graphs are of this type. Thus, e. g., the following statements are equivalent for triangle free graphs G with 2.5 α(G) ⩽ n(G) ⩽ 3 α(G):

(i) G is edge number critical with respect to α(G) and n(G),
(ii) e(G) − 5n(G) + 10 α(G) = 0,
(iii) G is a sum of chains and bicycles.

(The equivalence between (i) and (ii) yields the 5n − 10k part of proposition 1.)

Radziszowski and Kreher discussed whether there could be an exhaustive set of intervals a_{i} α(G) ⩽ n(G) ⩽ a_{i+1} α(G) and linear inequalities e(G) − b_{i}n(G) + c_{i} α(G) ⩾ 0, such that for each interval the edge critical graphs are precise those with equality in the corresponding inequality, at least for large enough n(G). Now, in this strong formulation, this certainly is not the case. The ‘correct interval’ for the linear inequality (1) would be 3 α(G) ⩽ n(G) ⩽ 3.25 α(G), as seen from their own results and from theorem 3. However, if 3.25k − 1 < n < 3.25k and k ⩾ 5, then e(3, k + 1; n) = 6n − 13k + 1; and such integers n do exist for arbitrarily large k not divisible by 4. Thus, the best we could hope for is some kind of proportional result.

With fixed k, n, and e = e(3, k + 1; n), we may compare the proportions a = \frac{n}{k} and b = \frac{e}{k}. By linearity, indeed then e(3, mk + 1; mn) ⩽ me for any positive integer m. (In fact, if G is (3, k + 1; n, e) realising then clearly mG is (3, mk + 1; mn, me) realising.) By this and similar considerations, in the limit we may consider b as a function of a, and this function is convex.

Formally, for any real number a ⩾ 0, let

b(a) = lim_{k→∞} \frac{e(3, k + 1; ⌊ak⌋)}{k}

(where as usual ⌊ak⌋ is the integer part of ak). The enumerated linear inequalities imply that b is piecewise linear for 0 ⩽ a ⩽ 3.25, and in fact that there

the electronic journal of combinatorics 16 (2009), #R00 21

b(a) = max(0, a − 1, 3a − 5, 5a − 10, 6a − 13) .

What we could hope for, and what Radziszowski and Kreher implicitly suggest, is, that b continues to be piecewise linear in its whole domain.

To be more precise, they express their suggestions in terms of the independence ratio \frac{k}{n} as a function of the average degree \frac{2e}{n}, instead of \frac{e}{k} as a function of \frac{n}{k}. Thus, in the limit, they define a decreasing function i^{∗} = i^{∗}(x). The relations between the ratios are respected by the limits, whence i^{∗} may be defined in terms of b, and vice versa. In fact, for a > 1, if x = \frac{2b(a)}{a}, then i^{∗}(x) = \frac{1}{a}; and if a = \frac{1}{i^{∗}(x)}, then b(a) = \frac{x}{2i^{∗}(x)}. Thus, close to a point (a_{0}, b_{0}) and the corresponding point (x_{0}, i_{0}^{∗}), we have

i^{∗} is linear in x
⟺ x is linear in i^{∗}
⟺ \frac{x}{i^{∗}} is linear in \frac{1}{i^{∗}}
⟺ b is linear in a.

Thus, indeed the function i^{∗} is piecewise linear (in its whole domain) if and only if b is.

However, whether or not these functions indeed are piecewise linear seems to be a hard question. On the other hand, it is not very hard to prove that b is continous, convex, and non-decreasing, and that it has both left and right derivatives in its whole domain (except to the left at the origin), and that moreover these derivatives are non-decreasing, and that for any positive a_{0} the left derivative for a_{0} is less than or equal to the right derivative for a_{0}, but greater than or equal to the right derivative for any a < a_{0}. In fact, all the other properties are consequences of the convexity and of b being constant in an interval containing the minimum of its domain.

For the convexity, it is sufficient to note, that for any 0 ⩽ a_{0} < a < a_{1} and any ϵ > 0

b(a) ⩽ \frac{b(a_{1}) − b(a_{0})}{a_{1} − a_{0}}a + \frac{b(a_{0})a_{1} − b(a_{1})a_{0}}{a_{1} − a_{0}} + ϵ,

by considering graphs G_{0} and G_{1} with n(G_{i})/ α(G_{i}) and e(G_{i})/ α(G_{i}) approximating a_{i} and b(a_{i}) sufficiently well, and a suitable linear combination G = m_{0}G_{0} + m_{1}G_{1} with n(G)/ α(G) slightly larger than a.

That the graph of b is convex also may be reformulated thus: For every c ∈ [0, ∞[ , there is a unique number d ∈ [0, ∞[ , such that the line b − ca + d = 0 touches but does not intersect the graph. In other words,

d = d(c) = max (y : b(a) ⩾ ca − y ∀ a) = min (y : ∃ a such that b(a) = ca − y) .

Hence, for each c there is a “best” linear graph invariant ℓ_{c}(G) = e(G) − cn(G) + dαG, which is non-negative for all triangle free graphs. (In fact, if there were a triangle free G with ℓ_{c}(G) < 0, then b(a) < ca − d for a = \frac{n(G)}{α(G)}, against the assumptions.) Correspondingly, with the same c and d,

i^{∗}(x) ⩾ \frac{c}{d} − \frac{1}{2d}x

[figure: The function graph for b(a), as far as known:; a; b; 1; 2; 2.5; 3; 3.25; 4; 1; 2; 2.5; 3; 4; 5; 6; 6.5; 7]

is an ‘optimal’ linear lower bound for Radziszowski’s and Kreher’s function i^{∗}.

For each such c, there either is a unique a = a_{c} with b(a) = ca − d, or there are several such a. In either case, necessarily c is at least the left derivative and at most the right derivative of b at each such a. Thus, if there are several such a for a fixed c, they indeed form an interval, and b is differentiable with b′(a) = c in the interior of this interval, and thus is linear there.

Thus, in order to determine b also for some interval 3.25 ⩽ a ⩽ A, we may equivalently determine the left and right derivatives in this interval (excepting the right derivative at A), or determine the ℓ_{c} for all c less than or equal to the left b derivative at A. The first question would be the value r, say, of the right derivative of b at a = 3.25. Since this is at least equal to the left derivative, and since on the other hand e. g. e(3, 7; 21) = 51 ⟹ b(3.5) ⩽ 8.5,

6 ⩽ r ⩽ 8 .

In fact, for 3.25k ⩽ n ⩽ 3.5k, there are numerous realisers of (3, k + 1; n, 8n − 19.5k); including all linear combinations of W_{13;1,5} and crochet graphs with crochet patterns containing only trivalent vertices. On the other hand, there is in my knowledge no known triangle free graph G for which

ℓ(G) := e(G) − 8n(G) + 19.5 α(G)

is negative. Indeed, there is no such graph with α(G) < 10, as can be seen from the exact values and estimates of e-numbers in [2]. In fact, also employing the e-number tables in [1], the smallest possible counterexample would be a (3, 11; 35, 84) realiser G; if it did exist, it would have ℓ(G) = −1. In view of the behaviour for lower independence and vertex numbers, it would be a bit of a surprise to have such a large simplest example of a negative value for ℓ.

Thus, I think it is a reasonable guess that r = 8, or, equivalently, that ℓ_{8} = ℓ, or

b(a) =^{?} 8a − 19.5 for 3.25 ⩽ a ⩽ 3.5 .

I have tried to prove this by means of the same kind of strategy as the one used in this article, but this seems hard. My best result so far is that

r ⩾ 6.8, i.e., e(G) − 6.8e(G) + 15.6 α(G) = ℓ_{6.8}(G) ⩾ 0

for all triangle free G ([1, proposition 12.5]^{7} and its first corollary). However, both the proposition and its proof are fairly complex; I found no simpler way than making a simultaneous induction over statements for graphs G with over forty distinct upper bounds on ℓ_{6.8}(G). (Thus, just the formulation of the proposition covers three typeset pages, and the proof of the induction ten times more, preparatory results uncounted.)

Granted these results, we at least have e. g. that 8.2 ⩽ b(3.5) ⩽ 8.5. Minor improvements of the bounds for r, and for b in the interval [3.25, 3.5] should be possible with these methods; but for substantial improvements, probably new ideas are needed, or an improved interaction between theoretical analysis and computer assisted investigation.

References

[1] J. Backelin, Contributions to a Ramsey calculus, unpublished manuscript.

[2] J. Goedgebeur and S. P. Radziszowsky, New computational upper bounds for Ramsey numbers R(3, k), Electronic Journal of Combinatorics 20(1) (2013).

[3] A. Lesser, Theoretical and computational aspects of Ramsey theory, Examensarbeten i Matematik, Matematiska Institutionen, Stockholms Universitet 3 (2001).

[4] S. P. Radziszowski and D. L. Kreher, On (3,k) Ramsey graphs: Theoretical and computational results, J. Comb Math. and Comb. Computing 4 (1988), 37–52.

[5] S. P. Radziszowski and D. L. Kreher, Minimum triangle-free graphs, Ars Comb. 31 (1991), 65–92.

7Actually, in order to work with integer valued invariants, the proposition is formulated in terms of an invariant c(G) := 5ℓ_{6.8}(G) = 5e(G) − 34n(G) + 78 α(G).

the electronic journal of combinatorics 16 (2009), #R00 24