Maximum degree in maximal triangle free graphs

Question

It's easy to see that in bipartite maximal triangle free graphs (n vertices), the maximum degree is at least $\lceil n/2 \rceil$. What about mtf graphs in general? Must there always be some vertex of high degree? Before I jump in with both feet, is there an obvious reason why there cannot be an absolute constant $c$ such that for every mtf $G$, $\Delta(G) > cn$? A handy counterexample to c = 1/4?

Answer 1

There is a sequence of Kneser graphs, generalizing the Petersen graph, that comprises a counterexample.

Let $k \ge 1$ be an integer and let $G$ be a graph whose vertices are subsets of size $k$ of $\{1,2,\ldots,3k-1\}$. Connect two vertices $A$ and $B$ by an edge if they are disjoint as subsets. Then $G$ has no triangles, because there isn't room for three disjoint subsets. On the other hand, if $A$ and $B$ are not connected by an edge, which is to say they are not disjoint, there is room for a third set $C$ which is disjoint from both of them. Thus if you add any edge $(A,B)$ to this graph $G$, it forms a triangle with $(A,C)$ and $(B,C)$.

Now let's count vertices and edges. The graph $G$ has $\binom{3k-1}{k}$ vertices, and each vertex has $\binom{2k-1}{k}$ edges. QED

(It is the Petersen graph when $k=2$.)

---

This is partly plagiarizing from David's insightful answer below, but I can't resist an addendum to his remarks. In the paper, The triangle-free process, Tom Bohman simplifies the construction of Kim that David cites. He makes a maximal triangle-free graph on $n$ vertices in using simplest plausible method: The random greedy algorithm. The result is a graph that is statistically very predictable. Its independence number is almost always $\Theta(\sqrt{n \log n})$, and therefore so is its maximum valence. Its average valence is also in the same class. You can easily make graphs like this yourself with a simple computer program and see their properties. It's ironic, but a common theme, that a very simple random algorithm is more efficient than a highly symmetric construction such as the Kneser graphs.

As David explains, you get an immediate lower bound of maximum valence $\Omega(n^{1/2})$ for any graph of diameter 2 or even radius 2. The Kneser graphs above have valence $O(n^\alpha)$ with $\alpha = \log_{27/4}(4) \approx 0.726$. So the Kim-Bohman result is much stronger, and that's why he pointed out Kim's paper.

In fact, this result closes a circle for me. A triangle-free graph on $n$ vertices is also a type of "packing design" in which each triple of vertices only has room for two edges. The original paper that introduced the random greedy algorithm in the topic of packing designs is by Gordon, Kuperberg, Patashnik, and Spencer. In that paper, we were looking at packing designs at the opposite end, for instance choosing triples of points with a random greedy algorithm such that no edge is contained in more than one triple. (The paper says covering designs, but at our end of the asymptotics, they are almost the same as packing designs.) It's the same highly predictable phenomenon at both ends. One of the ideas in this paper was to simplify a fancier construction using "Rödl nibbles" to the random greedy algorithm. Bohman is doing the same thing (but with much stronger asymptotics than in our paper), because Kim also uses Rödl nibbles.

Answer 2

A maximal triangle-free graph has diameter two, so its breadth-first spanning tree has a vertex with a number of children that is at least proportional to $\sqrt n$.

I have the feeling that it should be possible to cook up a matching $O(\sqrt n)$ upper bound on the maximum degree, by using incidence graphs of the points and lines in a projective plane, but that doesn't quite work: it is triangle-free (and bipartite), has maximum degree $O(\sqrt n)$, and prevents adding any more point-point or line-line edges, but there is no obstacle to adding more point-line edges.

(Edit to add, after Greg left a comment on an earlier version of this answer): See the Kim 1995 reference from http://en.wikipedia.org/wiki/Triangle-free_graph:

Kim, J. H. (1995), "The Ramsey number $R(3,t)$ has order of magnitude $\frac{t^2}{\log t}$", Random Structures and Algorithms 7: 173–207 .

He describes a construction for a triangle-free graph in which every independent set has size $O(\sqrt{n\log n})$. If one makes the graph maximal, this doesn't increase the size of its independent sets. But in a triangle-free graph, the neighbors of every vertex form an independent set, so the maximalized version of Kim's graph has degree $O(\sqrt{n\log n})$.