4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Laars Helenius Apr 7 '16 at 2:18
  • $\begingroup$ 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! $\endgroup$ – Laars Helenius Apr 7 '16 at 2:51
  • $\begingroup$ 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. $\endgroup$ – sidhant Apr 7 '16 at 5:05
  • $\begingroup$ 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. $\endgroup$ – bof Apr 7 '16 at 5:39
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How would a triangle necessarily be formed if there was an edge between two vertices of $V(G)-N_G(v)$? $\endgroup$ – Casteels Apr 6 '16 at 17:26
  • $\begingroup$ 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$. $\endgroup$ – Laars Helenius Apr 6 '16 at 17:39
  • $\begingroup$ I have edited my answer to clarify this. $\endgroup$ – Laars Helenius Apr 6 '16 at 17:52
  • $\begingroup$ 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$? $\endgroup$ – Casteels Apr 6 '16 at 18:02
  • $\begingroup$ 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 $\endgroup$ – sidhant Apr 7 '16 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.