Suppose that a graph consists of m vertices, all of which have the same degree n $\geq$ 0. The graph can consist of disjoint, connected components, and there is at most one edge between any two vertices. How would I prove that there if there aren't any cycles of exactly 3, the graph must have 2n vertices?
I was planning on doing induction on $m$(the vertices), and trying to use the handshaking lemma to sum the degrees. But I am stuck at the induction step!
On
Induction generally works pretty badly on regular graphs (graphs in which every vertex has the same degree). Induction on graphs is all about the idea that to deal with an $m$-vertex graph, you delete a vertex and apply the inductive hypothesis to the $(m-1)$-vertex graph. But in this case, if you delete a vertex from a regular graph, the remainder is no longer regular, so the inductive hypothesis does not apply.
If you stick with the idea of induction, you want to generalize the claim. We can try to prove that in any graph which has no length-$3$ cycles, and in which every vertex has at least $n$ neighbors, there must be at least $2n$ vertices total.
If we make this an induction on $n$, then (knowing what the final answer looks like) we want to delete $2$ vertices from a graph with this property. To apply the inductive hypothesis, we want to do it in such a way that in the remainder, every vertex still has degree at least $n-1$. Then, by the inductive hypothesis, the remainder has at least $2(n-1)$ vertices; together with the vertices we deleted, the original graph must have at least $2n$ vertices.
Now there is only one thing you need to figure out to make this work. How to choose two vertices to remove from such a graph, so that every degree in the remainder doesn't go below $n-1$?
On
Well, if you show the following:
A graph $G$ with $N$ vertices and with average degree greater than $\frac{N}{2}$ or equivalently with more than $\frac{N^2}{4}$ edges (no need to assume regularity) has a triangle
then this will immediately imply what you are trying to establish.
To this end, let us assume that $G$ is triangle-free and attempt to upper-bound the number of edges $G$ can have. To this end, $xy$ be an edge in $G$, and let $U_x$ be the set of vertices $v \not = y$ adjacent in $G$ to $x$ and let $U_y$ be the set of vertices $v \not = x$ adjacent in $G$ to $y$.
Then as $G$ is triangle free $U_x$ and $U_y$ are disjoint sets [make sure you see why] and furthermore $U_x$ and $U_y$ are independent sets in $G$ [make sure you see why]. Then the most edges $G$ can have is $|U_x||U_y| + |U_x|+|U_y|+ 1$. But because $U_x$ and $U_y$ are disjoint, it follows that $|U_x|+|U_y|$ is bounded by $N-2$ [make sure you see why] so this is at most $\frac{(N-2)^2}{4}+N-2+ 1$ which is no larger than $\frac{N^2}{4}$. So $G$ triangle-free implies no more than $\frac{N^2}{4}$ edges.
And this bound is tight for even $N$, consider the complete graph w $\frac{N}{2}$ vertices on one side and $\frac{N}{2}$ vertices on the other side.
**If you sketch through this proof can you find a tight bound on the number of edges in a triangle-free graph on $N$ vertices for odd $N$?
On
Consider vertex labelled $1$. This is connected to vertices $2,3,\dots,n+1$ because it has $n$ neighbours. Now, for $2\leq i<j\leq n+1$, $i$ and $j$ cannot be neighbours because if they were, then $(1,i,j)$ is a 3-cycle. Thus, the neighbours of vertex $2$ include vertex $1$ and $n-1$ vertices other than $1,2,\dots, n+1$. Thus we already have $(1)+(n)+(n-1)$ vertices [$1$ count for vertex $1$. $n$ count for vertices $2,\dots,n+1$. $(n-1)$ count for the neighbours of vertex $2$ other than vertex $1$]. Thus $m\geq1+n+n-1=2n.$
Let $xy$ be an edge of $G$. Each of $x$ and $y$ has $n-1$ neighbours in $V(G) - x - y$. The set of neighbours of $x$ and $y$ are disjoint, otherwise $G$ will have a triangle. Therefore, $|V(G) - x- y|\geq 2(n-1)$. Hence $|V(G)| \geq 2n$