Return to Answer

The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. If $G$ is not just a cycle, then $G$ contains a cycle and an ear. However, by parity considerations, a cycle and an ear always contains an even cycle.

Now let $G$ be an arbitrary even-cycle-free graph and consider its block-cut-tree $T$. By the previous remark, each block of $G$ is an odd cycle or just an edge. To maximize the number of edges, each block of $G$ should be a triangle. Thus, the maximum number of edges is attained by a 'tree of $k$ triangles.' This graph has $3k$ edges and $2k+1$ vertices.

The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. If $G$ is not just a cycle, then $G$ contains a cycle and an ear. However, by parity considerations, a cycle and an ear always contains an even cycle.

Now let $G$ be an arbitrary even-cycle-free graph and consider its block-cut-tree $T$. By the previous remark, each block of $G$ is an odd cycle or just an edge. To maximize the number of edges, each block of $G$ should be a triangle. Thus, the maximum number of edges is attained by a 'tree of $k$ triangles.' This graph has $3k$ edges and $2k+1$ vertices. For $n$ even (say $n=2k+2$), the maximum is attained when $T$ has exactly $k$ blocks which are triangles and exactly one block which is an edge. This is a complete characterization of the extremal examples.

The answer is $\lfloor \frac{3}{2}n \rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. If $G$ is not just a cycle, then $G$ contains a cycle and an ear. However, by parity considerations, a cycle and an ear always contains an even cycle.

Now let $G$ be an arbitrary even-cycle-free graph and consider its block-cut-tree $T$. By the previous remark, each block of $G$ is an odd cycle or just an edge. To maximize the number of edges, each block of $G$ should be a triangle. Thus, the maximum number of edges is attained by a 'tree of $k$ triangles.' This graph has $3k$ edges and $2k+1$ vertices.

The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. If $G$ is not just a cycle, then $G$ contains a cycle and an ear. However, by parity considerations, a cycle and an ear always contains an even cycle.

Now let $G$ be an arbitrary even-cycle-free graph and consider its block-cut-tree $T$. By the previous remark, each block of $G$ is an odd cycle or just an edge. To maximize the number of edges, each block of $G$ should be a triangle. Thus, the maximum number of edges is attained by a 'tree of $k$ triangles.' This graph has $3k$ edges and $2k+1$ vertices.

The answer is $\frac{3}{2}n$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. If $G$ is not just a cycle, then $G$ contains a cycle and an ear. However, by parity considerations, a cycle and an ear always contains an even cycle.

Now let $G$ be an arbitrary even-cycle-free graph and consider its block-cut-tree $T$. By the previous remark, each block of $G$ is an odd cycle or just an edge. To maximize the number of edges, each block of $G$ should be a triangle. Thus, the maximum number of edges is attained by a 'tree of $k$ triangles.' This graph has $3k$ edges and $2k+3$ vertices.

The answer is $\lfloor \frac{3}{2}n \rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. If $G$ is not just a cycle, then $G$ contains a cycle and an ear. However, by parity considerations, a cycle and an ear always contains an even cycle.

Now let $G$ be an arbitrary even-cycle-free graph and consider its block-cut-tree $T$. By the previous remark, each block of $G$ is an odd cycle or just an edge. To maximize the number of edges, each block of $G$ should be a triangle. Thus, the maximum number of edges is attained by a 'tree of $k$ triangles.' This graph has $3k$ edges and $2k+1$ vertices.