Given that, a graph G is connected. Every simple circuit, that does not pass through any vertex (except the initial vertex) more than once, contains an odd number of edges.
To prove: G is a cactus.
Let G not be a cactus.
Then there exists an edge \(e = \left\{ {u,v} \right\}\) in G that is contained in two different simple circuits \({C_1}\) and \({C_2}\).
These simple circuits are then of the following form (where \({P_i}\) represents some path).
\(\begin{array}{l}{C_1} = u,{P_1},x,{P_2},y,{P_3},v,e,u\\{C_2} = u,{P_1},x,{P_4},y,{P_3},v,e,u\end{array}\)
Note:
- It is possible that \(u = x\)and/or\(v = y\), then the path between the two variables (that are the same) is non-existent.
- The two different circuits only differ in the path between x and y.
Since every simple circuit in G, that does not pass through any vertex (except the initial vertex) more than once, contains an odd number of edges, \({C_1}\) and \({C_2}\) both contain an odd number of edges.
Since \({C_1}\) and \({C_2}\) only differ in the paths \({P_1}\) and \({P_3}\), \({P_2}\) and \({P_4}\) both have to be odd or both have to be even.
However, we then obtain a simple circuit consisting of \({P_2}\) and \({P_4}\) backwards which needs to have an even number of edges, since the sum of two odd integers is even and the sum of 2 even integers is even too).
We have then derived a contradiction as G did not contain a simple circuit, that does not pass through any vertex (except the initial vertex) more than once, contains an odd number of edges.
Hence proved that G has to be a cactus.
