I am trying to work on this problem that I have: A cactus is a connected graph is which every block is an edge or a cycle. Prove that the maximum number of edges in a simple $n$-vertex cactus is $\left\lfloor{\frac{3(n-1)}{2}}\right\rfloor$. This requires both proving an upper bound and showing that it can hold with equality. (Hint: $\left\lfloor{x}\right\rfloor+\left\lfloor{y}\right\rfloor\leq\left\lfloor{x+y}\right\rfloor$).
So my approach is that we know since a cactus is connected, it has a spanning tree which has $n-1$ edges. Then I am thinking to somehow show that there are at most 3 spanning trees and they share half their edges. I am not too sure of how to go on from there. Also it says that after I show that the number of edges is at most $\left\lfloor{\frac{3(n-1)}{2}}\right\rfloor$, in order to show equality I basically need to construct a cactus with exactly that many edges for any number of vertices $n$. I have tried to do that but I can't think of a construction and I have a feeling that the answer to the first part should help me with the construction. Any help would be appreciated.
You can achieve that bound with a graph having only triangles as components and an additional single edge component in case $n \pmod 2 = 0$ (you can also turn one of the triangles into a square instead and achieve the same bound). doesn't really matter how you order that graph. I will leave the proof that any other structure is sub-optimal to the one I specified for you.