Contraction
===============

Contraction is an operation in graph theory where we consider a cycle in a graph, replace its vertices with a single new vertex, and for every vertex outside the cycle that was connected to any vertex in the cycle, we create an edge between that external vertex and the new vertex.

Suitable Choice for Contraction
------------------------------

The cycle we wish to contract should preferably contain no internal edges, so that after contraction, the graph remains simple. For example, triangles in a kite-free graph or the girth of a graph (if it has more than four vertices) possess these properties and are thus suitable candidates for contraction.

An Example
----------
Consider a simple graph whose cycles do not share edges and has :math:`2n+1` vertices. What is the maximum number of edges in this graph?

Answer
:math:`3n`

Example
~~~~~~~
As an example with this number of edges, you can place a vertex at the center of the graph and create a triangle containing this vertex for every pair of vertices.

.. _proof-of-maximality:

Proof of Maximality
~~~~~~~~~~~~~~~~~~~
Here we prove by induction that in any graph whose cycles share no common edges,  
the inequality :math:`2m \le 3n-1` holds.  

Consider the smallest counterexample to this theorem. This graph cannot be acyclic, because in that case,  
its number of edges would be less than its number of vertices, meaning the inequality holds.  
Clearly, the cycles of this graph cannot have chords (i.e., edges inside them),  
as this would create two cycles sharing an edge. Additionally, a vertex cannot have edges to two vertices  
of the same cycle.  

Now, contract one of the cycles in this graph. The graph remains simple, and it can be shown that  
its cycles still share no edges. (Prove this to gain intuition about contraction.)  
Since we assumed the smallest counterexample, the inequality holds for the contracted graph.  
If a cycle of length *k* is contracted, *k* edges and :math:`k-1` vertices are removed from the graph.  
Thus, we have:  

.. math:: 2(m - k) \le 3(n - k + 1) - 1  

From the original assumption, we know:  

.. math:: 2m > 3n - 1  

Combining these two inequalities yields:  

.. math:: 2k < 3(k - 1)  

This implies that the contracted cycle had fewer than 3 vertices, which is impossible in simple graphs.  
This leads to a contradiction. Closer inspection reveals that equality occurs only when *k* is exactly 3,  
meaning all cycles in the graph are triangles (as seen in our earlier example).