Let $T$ be a triangle-free graph on $n$ vertices with minimum degree $\delta$ (which can be $0$). How does one show that $n >2\delta -1$? It seems to be true for bipartite graphs, but I cannot see how to prove it for general triangle free graphs in general. The motivation behind this question is if this is solved, I will have a much more interesting corollary to garner from it. Thank you!
Triangle Free Graphs – Minimum Degree Relationship
graph theorytriangles
Related Solutions
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.
yes, it feels like one could proof my characterization along the following lines:
If the graph does not contain $K_4^-$, then it is a line graph of a 3-regular graph.
Now continue with a copy of $K_4^-$. The two vertices of degree three must each be incident to another edge. If these two edges meet, then we can reduce the whole structure to a triangle like you describe (my $K_{3,1,1}$).
If the two edges do not meet, then they each must lie in a triangle, so there need to be edges from their endpoints to the vertices of degree 2 in the $K_4^-$. If both these edges meet in the same vertex, we again have a structure we can reduce to a triangle (a triangle in the line graph original, which we can contract keeping 3-regularity).
So we are left with the case where the two edges go to different sides of the $K_4^-$, and again we have two vertices of degree 3 to work with. If these two vertices are connected, then we have a $K_4$ with two triangles attached to it which we can get from the multi-line-graph of edge-doubleedge-edge by $K_{3,1,1}$ing one of the triangles (or alternatively, we can reduce the whole graph by contracting the whole structure to one vertex).
If these two vertices are not connected, then each must lie in a triangle with the neighboring vertex of degree 2, and this process will go on until the two sides meet in a cycle, in which case you got your square of a cycle.
Best Answer
In addition to the literature mentioned in the other answers, one can try some arguments based on counting.
Let $u$ and $v$ be two of $n$ vertices in a triangle-free graph, and further assume they are distinct and connected by an edge, with degrees $c$ and $d$ and $c$ at most $d$. Then their neighborhoods are disjoint, so $c - 1 + d - 1$ is at most $n-2$, giving $2\delta \leq n$.
It might be fun to recreate the $2n/5$ result: here is a start. Take an odd cycle from a non bipartite graph with minimal cycle length. If the cycle length is $7$ or greater, show that three vertices will produce either a triangle, a shorter odd length cycle, or a degree at most $2n/5$. Try a similar analysis with a $5$-cycle. Enjoy!