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?
[Math] Maximum degree in maximal triangle free graphs
co.combinatoricsgraph theory
Best Answer
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.