MathDB

Let

\mathcal{G}

be a simple graph with

n

vertices and

m

edges such that no two cycles share an edge. Prove that

2m < 3n

.
Note: A simple graph is a graph with at most one edge between any two vertices and no edges from any vertex to itself. A cycle is a sequence of distinct vertices

v_1, \dots, v_n

such that there is an edge between any two consecutive vertices, and between

v_n

and

v_1

.
Proposed by Ethan Tan

Problem Statement