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.
 A: 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).$$
A: 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. 
