# Upper bound on the number of edges of a ten vertexes graph no $C_4, C_3$ subgraph.

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.

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.