Bound for graph's size with cycles

I have the following problem:

Let $G$ be a simple graph with $n$ vertices and such that every cycle in $G$ has length $\leq3$. Then $e(G)\leq\dfrac{3(n-1)}{2}$. (where $e(G)$ is the number of edges of the graph $G$)

I think it could be a good idea to prove this by induction, but do not know how to use the bound for the length of the cycles.

• I don't understand, if graph is simple how can it have 2 cycle? Or I don't understand the term simple. Commented Nov 3, 2017 at 15:06
• Simple means that the graph is undirected, unweighted and is not a multigraph (graphs with more than one edge between vertices)
– plr
Commented Nov 3, 2017 at 15:53
• So the only cycles wich are possible are 3-cycles? Commented Nov 3, 2017 at 15:55
• Yes, that's correct. Because 2-cycles will mean that 2 vertex are joined by 2 edges, and we do not allow them here.
– plr
Commented Nov 3, 2017 at 16:31

Suppose graph has 3-cycles $C_1,C_2,...C_k$ and $\varepsilon$ edges. Each cycle has 3 edges and because of condition that each cycle is of length 3 every edge is in at most one 3-cycle. So we have $$k\leq {\varepsilon\over 3}$$

Suppose graph has spanning sub tree $T$ which has exactly $n-1$ edges. Then each edge which is not in $T$ (we have $\varepsilon -n+1$ of those) must be on exactly one 3-cycle. But we can't have more those edges than the 3-cycles. So we have $$\varepsilon -n+1\leq k \leq {\varepsilon\over 3} \Longrightarrow \varepsilon \leq {3n-3\over 2}$$

• For greater generality, we can let $T$ be a full spanning forest (the union of spanning trees on each connected component). This still has at most $n-1$ edges (fewer if the graph is not connected) and is still a maximal acyclic subgraph. Commented Nov 3, 2017 at 16:22
• Yes, yes, I assumed graph is connected. But if not you can proceed as you said. Commented Nov 3, 2017 at 16:28
• @JohnWatson, when you say "Then each edge which is not in T (we have $\epsilon - n +1$ of those) must be on exactly one 3-cycle", I do not see why this is true.
– plr
Commented Nov 3, 2017 at 18:05
• Say we have an edge $AB$ which is on two 3-cycles, say $ABC$ and $ABD$. But then we have a 4-cycle $ADBC$. It is exactly the same argument as I had when I count the number of all possible 3-cycles. Commented Nov 3, 2017 at 18:08
• Yes, I understand that if one is in two 3-cycles, you have a 4-cycle; but why having those edges in $T$ makes them unable to be on a 3-cycle. You can have a spanning tree with edges that belong to a cycle, can't you? I do not see the implication "edge in tree" $\rightarrow$ "edge not in cycle".
– plr
Commented Nov 3, 2017 at 19:25