Graph Theory - No 3-cycles - Maximum degree k.

I encountered this problem on one of the assignments from an introductory course to graph theory (not a course I am taking so I am not asking anybody to do my homework :p).

Suppose that $G$ has $p$ vertices, $q$ edges, maximum degree $k$ and no cycles of length $3$. Prove that $q \leq k(p-k)$

The way I thought of it was to start with the vertex with degree $k$ and then reason about the possible number of neighbours it had and the neighbours of those neighbours but since there is no set structure to the graph I could not think of a way. Any pointers or hints would be great.

We assume, of course, that $G$ is a simple graph; otherwise the statement is false. Choose a vertex $u$ of maximum degree and let $U=V(G)\setminus N(u),$ so that $|N(u)|=k$ and $|U|=p-k.$ Since $G$ is triangle-free, $N(u)$ is independent; i.e., each edge of $G$ has at least one endpoint in $U.$ For $v\in V,$ let $E_v$ denote the set of edges of $G$ incident with $v.$ Then $$q=|E(G)|=\left|\bigcup_{v\in U}E_v\right|\le\sum_{v\in U}|E_v|=\sum_{v\in U}\operatorname d(v)\le\sum_{v\in U}k=k|U|=k(p-k).$$

• You say each edge of $G$ has at least one endpoint in $U$ (true) but then claim there at most $k(p-k)$ edges as a result. Don't you mean at least $k(p-k)$ edges? – Laars Helenius Apr 7 '16 at 2:18
• OK. I see what you are saying now. The difference in my proof compared to yours is that I focused on the vertices in $N(u)$ which made my proof (unnecessarily) more complicated. Well done! – Laars Helenius Apr 7 '16 at 2:51
• Thanks for the clear proof. It is really appreciated. I would like to know however that how did you approach the problem. What was your line of thinking. Thanks to Laars too for the earlier proof. – sidhant Apr 7 '16 at 5:05
• I didn't have to think about it. Thanks to my eons of experience, I've already seen, if not your exact problem, problems like it before, and I recognized the pattern. As soon as I saw you were asking about triangle-free graphs, I thought of the most famous theorem about triangle-free graphs, Turán's theorem, or rather its special case called Mantel's theorem, whose proof uses more or less the same trick, if you can call it a trick. Good question, sorry I can't give a more helpful answer. – bof Apr 7 '16 at 5:39

Suppose $G$ is a graph that is triangle free and $\Delta(G)=k$. Let $v\in V(G)$ such that $\operatorname{deg}(v)=k$ and consider $N_G(v).$

CASE I ($p-k\le k$): There cannot be any edges between any two vertices in $N_G(v)$, otherwise $G$ would have a triangle. So $N_G(v)$ is an independent set of vertices whose edges all go to the remaining $p-k$ vertices. Thus $G$ can have at least $k(p-k)$ edges. There cannot be any edges connecting vertices in $V(G)-N_G(v)$ otherwise a triangle would be formed. Thus the maximum number of edges is $k(p-k)$.

CASE II ($p-k>k$): There cannot be any edges between any two vertices in $N_G(v)$, otherwise $G$ would have a triangle. So $N_G(v)$ is an independent set of vertices whose edges are distributed amongst the remaining $p-k$ vertices. Thus $G$ can have at least $k^2$ edges. Now for each $u\in N_G(v)$ there are at least $p-2k>0$ vertices in $V(G)-N_G(v)$ that are not in $N_G(u)$ and we can add these edges into $V(G)-N_G(v)$ without creating triangles. So we can add at least $k(p-2k)$ more edges to $G$ so that we have at least $k^2+k(p-2k)=k(p-k)$ edges in $G$. If we try to add any more edges to $G$ we will either form a triangle by connecting two vertices in $N_G(u)$ for some $u\in N_G(v)$ or by connecting two vertices not in any $N_G(u)$. Thus the maximum number of edges is $k(p-k)$.

In either case, we are done.

• How would a triangle necessarily be formed if there was an edge between two vertices of $V(G)-N_G(v)$? – Casteels Apr 6 '16 at 17:26
• We are trying to figure out how many edges there can be. We know there are no edges connecting vertices $N_G(v)$. So the worst case scenario would be that every possible edge exists between $N_G(v)$ and $V(G)-N_G(v)$ for at most $k(p-k)$ edges. The only other place additional edges could arise is among the vertices of $V(G)-N_G(v)$. Let $w\in N_G(v)$ and let $u,v\in V(G)-N_G(v)$. So $wu, wv\in E(G)$. If $uv\in E(G)$ then $G$ would have the triangle $u,v,w$. – Laars Helenius Apr 6 '16 at 17:39
• I have edited my answer to clarify this. – Laars Helenius Apr 6 '16 at 17:52
• I guess my confusion is that it's unclear to me why one must have all the possible edges from $N_G(v)$ to $V(G)-N_G(v)-v$. Why can't it be that there are just a few, and then many within $V(G)-N_G(v)-v$? – Casteels Apr 6 '16 at 18:02
• The condition $p-k \leq k - 1$ is not true for all cases. For example, you could just take the graph I have attached and the inequality will be incorrect.awwapp.com/s/4932d5f3-a285-4773-afec-5ec2a1f1f2eb – sidhant Apr 7 '16 at 0:23