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.
On
The Petersen graph, which contains no cycle of length $3$ or $4$, has $10$ vertices and $15$ edges. I will show that $15$ is the maximum, and is attained (among graphs with $10$ vertices and no $3$-cycles or $4$-cycles) only by the Petersen graph.
Suppose $G$ is a graph with $10$ vertices and at least $15$ edges which contains no cycle of length $3$ or $4$. An acyclic graph on $10$ vertices has at most $9$ edges, so $G$ must contain a cycle. Let $k$ be the minimum length of a cycle in $G$, and let $C$ be a cycle in $G$ of length $k$; so $5\le k\le10$. Let $D=V(G)\setminus V(C)$.
Now, if a vertex $v$ in $D$ were joined to two vertices in $C$, then $v$ would be in a cycle of length $\lt k$, contradicting the minimality of $k$. Therefore, each vertex in $D$ is joined to at most one vertex in $C$. Since the cycle $C$ has $k$ edges (and no chords), there are at most $k+(10-k)=10$ edges with at least one endpoint in $V(C)$, so there must be at least $5$ edges joining two vertices in $D$. Hence $\binom{|D|}2\ge5$, i.e., $|D|\ge4$. However, a graph on $4$ vertices with no cycle of length $3$ or $4$ is acyclic, so it has at most $3$ edges. Therefore the only possibility is that $k=5$ and $|D|=5$.
Since an acyclic graph on $5$ vertices has at most $4$ edges, $D$ must contain a cycle, necessarily of length $5$, and that cycle can have no chords. Thus there are just $5$ edges joining two vertices in $D$, and $G$ has just $15$ edges all told.
We have shown that a graph, which has $10$ vertices and $15$ edges and contains no cycle of length $3$ or $4$, must consist of two vertex-disjoint $5$-cycles and a matching between them. It is easy to see that such a graph, if it contains no cycles of length $4$, must be the Petersen graph.
Alternatively, let $f(n)$ denote the maximum number of edges in a graph with $n$ vertices and no cycles of length $3$ or $4$. For $n\ge3$ the inequality
$$f(n)\le\left\lfloor\frac{nf(n-1)}{n-2}\right\rfloor\tag1$$
can be seen by counting in two ways the pairs $(v,e)$ where $v\in V(G)$ and $e\in E(G-v)$. Then, after verifying $f(6)=6$, we can use $(1)$ to show that $f(7)\le8$, $f(8)\le10$, $f(9)\le12$, and $f(10)\le15$.
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: \begin{eqnarray} 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\} \end{eqnarray} we get a graph with $10$ vertices and $15$ edges.