3
$\begingroup$

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

  • 1
    It 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 1

4

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.

  • 0
    no problem :P, good that you understood it2011-12-09