let $G$ be a simple graph on $n$ vertices such that $G$ has no cycle of length $4$. show that $e(G)\le \frac{n}{4}(1+\sqrt{4n-3})$ where $e(G)$ denotes the number of the edges of the graph $G$.
graph avoiding cycle of length 4
-
1Posting questions in the imperative like this is generally considered impolite. Please refer to http://meta.math.stackexchange.com/questions/1803/how-to-ask-a-homework-question . – 2011-12-08
-
1It might be of interest for you to think about graphs which have cycles of all lengths (pancyclic) graphs as well as those which are missing a cycle of exactly one length (almost pancyclic) - see: http://en.wikipedia.org/wiki/Pancyclic_graph for a discussion of these ideas. – 2011-12-08
1 Answers
I included a proof of what you want in a question of mine where I asked for a tighter bound if the graph avoids also cycles of length 3: (I use the convention $m:=e(G)$)
I try to show if $G$ has no subgraph $C_4$, then $m \leq \frac{n}{4}(1+\sqrt{4n-3})$. We can consider the amount $k$ of subgraphs of $G$ that look like $K_{1,2}$ (a "cherry"). Certainly if we (double) count those, considering a vertice in the center of the cherry, we get:
$$k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
Now if we don't allow squares a pair of vertices $\{v,w\}$ can be endpoints of only one cherry, otherwise we would have a cycle, therefore
$$\binom{n}{2} \geq k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$
Then due to convexity of $\binom{x}{2}$ and the Jensen-Inequality one might conclude now that $m \leq \frac{1}{4} \cdot \left(\sqrt{n^2 (4n-3)}+n\right) $.
This is a link to Jensen's inequality in case you don't know it.
Edit: As the operator asked for more details:
Define $\varphi(x):=\binom{n}{2}$, it is easy to see that $\varphi$ is convex. Therefore we have that
$$\varphi\left(\frac{\sum x_i}{n}\right) \le \frac{\sum \varphi (x_i)}{n} \iff \sum \varphi (x_i) \geq n\cdot \varphi\left(\frac{\sum x_i}{n}\right)$$
And therefore
$$\binom{n}{2} \geq \sum_{v\in V}\binom{\text{deg}(v)}{2} \geq n\cdot \binom{\frac{1}{n}\sum_{v\in V}\text{deg}(v)}{2}=n\cdot\binom{\frac{2m}{n}}{2}$$
Because the sum over all degrees of the nodes corresponds to twice the amount of edges. Expanding the binomial on both sides yields your result.
-
0I know Jensen's function, but would you please show me how to apply it here? every time I use it on this question I get $m\le \frac{n}{4}(1+2\sqrt{n})$. – 2011-12-08
-
0@goodarzmehr I tried to be a bit more explicit. I hope you understand it now. – 2011-12-08
-
0now I undrestand, thanks a lot :) – 2011-12-09
-
0no problem :P, good that you understood it – 2011-12-09