1. What does this mean?
2. You can do a brainless $$$O(\frac{nm}{w})$$$ solution using bitsets. Do you need something faster?

number of cycles is floor(n/3), number of edge floor(n/3)*3 + n-(floor(n/3)*3)+(floor(n/3)-1) it will graph n3 simple loops and bridges?

Edit: The following is not quite correct. Check the comment below from nor and the continuation.

Imagine starting with a tree. It has $$$N$$$ nodes and $$$N - 1$$$ edges. Now expand each node into a cycle of 3 nodes. You get $$$3N$$$ nodes and $$$4N - 1$$$ edges. So the number of edges for a graph with $$$3N$$$ nodes is $$$4N - 1$$$. When you remove one or two nodes, you have to break at most one cycle, thus you can get for a graph with $$$3N - 1$$$ nodes the maximum number of edges is $$$4N - 3$$$ and for $$$3N - 2$$$ nodes you have at most $$$4N - 4$$$ edges.

This I believe can be proven by an argument similar to the following:

Any two "adjacent" cycles must be connected through precisely one node. If there were two connections then there would be a cycle of length greater than 3. This structure looks like a tree, where each node is what you get when you contract each cycle to a node. Then if you focus on the tree, you get the thing above.

I am aware that it is not quite a proof, but I don't know how to state it.

For the second question, the answer is $$$\lfloor\frac{N}{3}\rfloor$$$. You can get it using a similar argument, any 3 nodes can be in at most one cycle.

since there is no restriction that the graph has to be connected, the union of $$$\frac N 3$$$ triangles would have $$$N$$$ edges (and $$$\frac N 3$$$ triangles).

if i understand your question correctly the answer of your first question is $$$\lfloor \frac{n-1}{2} \rfloor+n-1$$$ and the answer of your second question is $$$\frac{n-1}{2}$$$ example for both of them is that you connect vertex $$$(u,v)$$$ if $$$u=v-1$$$ or ($$$u=v-2$$$ && $$$ u \equiv 0 \pmod{2} $$$) (We number the vertices from 0 )like this picture $$$(n=9)$$$:$$$\newline$$$ $$$\newline$$$ and we can prove first question with bfs if we run bfs from vertex $$$ u $$$ We know that a vertex cannot have 2 neighbors in the previous layer (fact 1) Because if it has We know that those two vertices have a path length of more than 1(in previous layers), so despite this vertex and the two edges it has. We will have a cycle longer than 3 and also if a vertex have $$$x$$$ child in our bfs we know that all edge between them (include between childs) can be at most $$$x+\lfloor \frac{x}{2} \rfloor $$$ because we know that in children we can't have a path with length larger than 1 . so at most we have $$$\lfloor \frac{x}{2} \rfloor$$$ edges between them . and we have at most $$$x$$$ edge between this vertex and its childs because it has $$$x$$$ child $$$\newline$$$ now with fact 1 we have : $$$\sum child_i \le n-1$$$ (it can be disconnect) so we proved that we have at most $$$\lfloor \frac{n-1}{2} \rfloor+n-1$$$ edges $$$\newline$$$ For your second question, you can prove it with dfs in a simple way (count the back edge) Finally, sorry if my English is not good

This was a question in the endsem exam of discrete structures course i did a year ago. Still dont know how to solve it :(