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!
Best Answer
Well, if you show the following:
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$?