we change the problem from $ n (\geq 4)$ to $n (\geq 3)$ $G = (V, E)$, where $V$ = set of islands and $E$ = set of bridges as usual. First, every cycle is odd (which is the problem's condition) Notice that every two cycle cannot share a bridge. Step1. if $G$ has no cycles

Step 2. if $G$ has cycles

Comment

The problem is a version of this problem. I also have included it as Problem 2.3 in Olympiad Graph Theory.

Induct on $n$.(Trivial for $n=3$) Let a vertex $u$ in the graph and erase it. Then, the remaining graph can be represented as the union of connected components $G_1, \cdots, G_k$. Then all $G_i$ satisfies the three conditions. Denote the number of vertices in each component as $v_1, \cdots, v_k$. Lemma 1. $d(u, G_i)\leq 2$ pf) If there are three vertices $a, b, c$ in $G_i$ which are connected to $u$, both path connecting $a$ through $b$ and $b$ through $c$ should have odd lengths by the third condition. Thus, we can find an even length path connecting $a$ through $c$, contradicts to the third condition. Lemma 2. If $d(u, G_i)=2$, $|E(G_i)|\leq \frac{3(v_i-1)}{2}-\frac{1}{2}$ pf) Pick two vertices $a$ and $b$ in $G_i$ which are connected to $u$. Then, we can find an odd length path $P$ connecting $a$ through $b$. We can also find that $P$ is a unique path connecting $a$ through $b$, otherwise we can find an even length cycle in either $G$ or $G_i$. If the length is larger than $1$, let $P=(w_0=a, w_1, \cdots, w_l=b)$. Note that $a$ and $w_2$ are not connected by an edge in $G_i$, since then we can find an even length path connecting $a$ through $b$, makes and even length cycle in $G$. Now I will add a new edge $e'$ connecting $a$ and $w_2$. If the new component $G_i'$ contains an even length cycle containing $e'$, there should be an odd length path connecting $a$ through $w_2$ in $G_i$, also contradicts. Hence, $G_i'$ also satisfies the three conditions, so $|E(G_i')|\leq \frac{3(v_i-1)}{2}$, $|E(G_i)|\leq \frac{3(v_i-1)}{2}-1$. Otherwise, $P$ should be an edge connecting $a$ and $b$. Now I will erase $P$, then $G_i$ would be divided into two connected components having $x$ and $y$ vertices. Since each components also safisfies the conditions, $|E(G_i)|\leq 1+\frac{3(a-1)}{2}+\frac{3(b-1)}{2}=\frac{3(a+b-1)}{2}-\frac{1}{2}=\frac{3(v_i-1)}{2}-\frac{1}{2}$. Denote $t$ be the numbers of $G_i$ such that $d(u, G_i)=2$. Then $|E(G)|\leq \sum{(|E(G_i)|+d(u, G_i))}\leq 2t+(k-t)+\sum\frac{3(v_i-1)}{2}-\frac{t}{2}=\frac{3(n-1)}{2}-\frac{k-t}{2}\leq\frac{3(n-1)}{2}$ (Equality holds for odd $n$, which the graph is a union of triangles which shares one vertex)

we just think whether there is a triangle in this graph if there exactly is a triangle so the other points can only connected to at most one point with the triangle and they also can't connect if they are connected to different points so it's easy to know that the number of the bridges is smaller than (3n-1)/2 and the rest is also easy to prove and we can use the example that one point in the centre and other points are all triangles and this solved#

terse writeup Use the obvious graph theoretic interpretation. Claim: We cannot have two odd cycles that share a contiguous subset of edges. Proof: Suppose we did. Take their symmetric difference to get an even cycle. Now partition all edges into $E$ and a spanning forest $F$. Construct a bipartite graph on $E$ and $F$ and draw an edge between $f \in F$ and $\overline{v_1v_2} \in E$ iff the (unique) path between $v_1$ and $v_2$ in $F$ contains $e$. By the claim every edge in $F$ has degree at most $1$, but every edge in $E$ has degree at least $2$, hence $|E|\leq |F|/2$ and we are done since $|F|\leq n-1$. $\blacksquare$ Remark: Obviously the key claim is not hard to naturally stumble upon, but in fact I initially worked with the spanning tree/forest idea for the entire problem, inspired by RMM 2019/3. It seems quite helpful if we have problems involving cycles in a sparse graph. In this particular case, though unnecessary, it essentially forces us to think about the problem in a certain way which makes reaching the claim basically inevitable. It turns out that it's not necessary to prove the claim itself, though, so in this proof we omit its introduction until later.

Instructive Problem! Take the trivial graph theory interpretation. Notice that we can not have $2$ odd cycles sharing a common subset of edges, else if we get an even cycle. Now take the spanning forest $F$ and the set of other edges $E$. We will build a bipartite graph on $E$ and $F$. Draw an edge between $t \in F$ and $v_1v_2 \in E$ if and only if the unique path between $v_1$ and $v_2$ in the spanning forest contains $t$. Since, by our observation every edge in $F$ has degree at most $1$, however in $E$ every edge has degree at least $2$, so $|E| \leq \frac{|F|}{2}$ and by using $|F| \leq n-1$ we're done. $\blacksquare$