1
$\begingroup$

We are given a graph $G$ with ten vertices. Any three or four vertices of $G$ don't form a cycle. What is the maximum number of edges $G$ could have?

I know that if the graph is planar and triangle free, it would have 16 edges. It seems that between any 4 vertices, there can be at most 3 edges.

Maybe there is a formula and can be proven by induction on number of vertex. I'm not sure.

$\endgroup$
1
$\begingroup$

Let $A$ be a set of connected pairs and $B$ a set of unconnected pairs of vertices in $G$.

Connect a pair of vertices $u,v$ with vertex $w$ iff $w$ is connected with both (that is we make a new graph which is bipartite).

Since there is no triangles we have $d(u,v) =0$ if $\{u,v\}\in A$ and

since there is no 4-cycles we have $d(u,v) \leq 1$ if $\{u,v\}\in B$

So we have $G$ $$0\cdot |A|+1\cdot |B| \geq \sum _{i=1}^{10} {d_i\choose 2}$$

By handshake lemma in starting graph $G$ we have $$\sum _{i=1}^{10} d_i = 2\varepsilon$$

where the number of edges in starting graph $G$ is $\varepsilon$. Since $|A|=\varepsilon$ we have $|B| = {10\choose 2} -\varepsilon$

Now we have by Cauchy inequality $$\sum _{i=1}^{10} {d_i\choose 2}\geq {1\over 2}({1\over 10}4\ \varepsilon^2 -2\varepsilon)$$

so $${10\choose 2} -\varepsilon\geq {1\over 2}({1\over 10}4\ \varepsilon^2 -2\varepsilon)$$

After solwing this quadratic inequality we get $\varepsilon \leq 15$.


This value can not be improved since we have a configuration for $\varepsilon = 15$. Say vertices are $1,2,...,10$ and let $N(v)$ be a set of neighours for $v$. Then if we set:

$$ N(1) = \{2,3,4\}$$ $$ N(2) = \{1,5,6\}$$ $$ N(3) = \{1,7,8\}$$ $$ N(4) = \{1,9,10\}$$ $$ N(5) = \{2,7,9\}$$ $$ N(6) = \{2,8,10\}$$ $$ N(7) = \{3,5,10\}$$ $$ N(8) = \{3,6,9\}$$ $$ N(9) = \{4,5,8\}$$ $$ N(10) = \{4,6,7\}$$

we get a graph with $10$ vertices and $15$ edges.

$\endgroup$

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.