Draw a few trees. How many edges at least need to be removed from the graph $\mathrm{K}_{4}$ to make it a tree?

## - Degree of a vertex, Handshaking Lemma -

The degree of a vertex is the number of edges emanating from that vertex. If we sum the degrees of all vertices, each edge is counted twice, since it always connects two vertices. Therefore, we have the following result:

Lemma 1.1. (Handshaking Lemma) The sum of the degrees of all vertices of a graph $G$ is equal to twice the number of edges of the graph.
At least one side must be removed because if we keep all four sides, it forms a cycle. Next, if we keep the two diagonals, we need to remove two more sides. Indeed, if we keep two adjacent sides, they will form a triangle with one of the diagonals, which results in a cycle. If we keep two opposite sides, they form a cycle with the two diagonals. In this case, we need to remove a total of 3 edges to obtain a tree. We get, up to rotation:

![](https://cdn.mathpix.com/cropped/2024_05_10_59677aa68548da326d08g-354.jpg?height=236&width=244&top_left_y=1454&top_left_x=905)

If we remove one of the diagonals but keep three sides, we will have a triangle formed by the remaining diagonal and two of the remaining sides. Therefore, we need to remove one of the sides. We get, up to rotation, one of the following drawings:

![](https://cdn.mathpix.com/cropped/2024_05_10_59677aa68548da326d08g-354.jpg?height=247&width=529&top_left_y=1866&top_left_x=771)

If we remove both diagonals, we get, up to rotation:

![](https://cdn.mathpix.com/cropped/2024_05_10_59677aa68548da326d08g-354.jpg?height=233&width=244&top_left_y=2193&top_left_x=905)

Thus, 3 is the minimum number of edges that need to be removed. Note that, up to deformation, we have obtained only two different types of trees.