Find the maximum number of edges of $G.$

Question

Given a positive integer n. Let $G$ be a simple, undirected graph with $ 2n +1 $vertices such that there is no cycle of length greater than $3.$ Find the maximum number of edges of $G.$

Mantel Problem : Deduce from the proof of Mantel theorem the following strengthening of the assertion. Let G be a triangle-free graph of order n. Then $ e(G)≤n^2/4$

I don't know if this problem has anything to do with mantel's problem, but if the graph doesn't have a cycle of degree $> 3$ then the graph can have a cycle of degree $3$. I tried a few small cases like $n = 1 ; n= 2 ;....$ then predict the answer to this problem is $3n$ . I hope I can get some help from everyone because I have no idea about this problem. Sorry for my ignorance!

Answer 1

Take such a graph, $G$, with possible triangles but no cycles length $4$ or greater.

Transform it into a new graph, $G'$ by taking each triangle and adding a new vertex and transforming it into a claw, that is to say... given a triangle $a,b,c$ with edges $ab,ac,bc$ replace it with vertices $a,b,c$ and a new vertex $x$ with edges $ax,bx,cx$.

transforms into

Now... one can easily see that such a transformation does not change the total number of edges. Further, this transformation removes all 3-cycles and since there were no cycles of length greater than 3 will then as a result have no cycles at all. The resulting graph is going to be a tree if connected and a forest in general.

The total number of vertices of the new graph will depend on the number of triangles of the original graph. The more triangles, the more vertices added.

Note that given a pair of vertices who are involved in a triangle together, they could only be in one triangle simultaneously since otherwise they would form a 4-cycle or greater.

Now, we hope to be able to describe every triangle in our original graph by some collection of disjoint pairs of vertices. A sketch of a proof might be to consider $G'$ and start contracting vertices starting from the leaves (which are guaranteed to exist by the fact $G'$ is a forest and has no cycles). Once you reach what was a triangle, you wait until two (or more) vertices of the original triangle are both ready to be contracted towards the corresponding newly added vertex for the triangle. Contracting them both, you can take note of them and these will be one of the pairs for the list of disjoint pairs of vertices used for describing our collection of triangles.

This all being said and done, we recognize then that we can have at most $n$ disjoint pairs of vertices and so at most $n$ triangles. We will have been able to add at most $n$ vertices then when transforming from $G$ to $G'$ while not changing the number of edges.

$G'$ has at most then $2n+1+n=3n+1$ vertices and as $G'$ is a forest has at most one fewer number of edges than vertices and so has at most $3n$ edges.

As $G$ has the same number of edges as $G'$ we see then that $G$ too must have at most $3n$ edges.

As for showing this upper bound is in fact tight and attainable, as mentioned in the comments, consider a central vertex connected to $n$ otherwise disjoint triangles. Such a graph does have $2n+1$ vertices and $3n$ edges.

Answer 2

Very briefly.

Let us prove that the maximal number $|E(G)|$ of edges of a connected graph $G$ of order $|V(G)|=2n+1$ with no cycles of length greater than 3 is at most $3n$. The proof will be by induction on $n$. If a graph has no triangles then it is a tree and the number of its edges is $n-1<3n$. Let $u,v,w$ be a triangle. Then the vertices $v$ and $w$ have no common neighbor except $u$ (otherwise the graph has a cycle of length 4). The same is true for pairs of vertices $u,v$ and $u,w$. Let $G'=G/\{u,v,w\}$ be obtained from $G$ by contracting vertices $u,v,w$ to vertex $v'$ (we remove vertices $u,v,w$ and add a new vertex $v'$, where the edges incident to $v'$ each correspond to an edge incident to either $u$, or $v$, or $w$). Then $G'$ is a simple graph with no cycles of length greater than 3. We have $|V(G')|=2n+1-3+1=2(n-1)+1$ and $|E(G')|=|E(G)|-3$. By induction $|E(G')|\leq3(n-1)$, so $|E(G)|\leq3n$.