# Prove the sufficient condition for a graph coloring problem.

We have a complete graph of n vertices. We need to remove all triangles one at a time preserving vertices. For which numbers n can we achieve this and how many triangles will we delete to get an empty graph?

Firstly, how many triangles will we delete? Since by removing 1 triangle we also delete 3 edges, we can say that the total number of edges is 3 times greater than the number of triangles. Also, we know that any complete graph has $\frac{n(n-1)}{2}$ edges. Thus, we will remove $\frac{n(n-1)}{6}$ triangles.

Secondly, when is it possible to remove all edges by deleting all triangles? Seeing that we have a complete graph of n vertices and we remove one triangle at a time, we can say that the number of edges should be a multiple of 3 (since one triangle has 3 edges), $\frac{n(n-1)}{2}\ mod\ 3\ = 0$. Otherwise, we will get at least 1 or 2 edges remaining after the deletion of all possible triangles.

When we delete a triangle we decrease the degree of 3 previously incident vertices by 2 (each vertex of a triangle has two edges). Therefore, in order to finish with zero available edges we should only have even vertex degrees in the graph. According to the fact that each vertex has an even degree that is equal to (n - 1), the number of vertices n should be odd.

We can delete all the edges from the initial graph by removing all triangles iff $n\ mod\ 2 \neq 0$ and​​ $\frac{n(n-1)}{2}\ mod\ 3\ = 0$.

$\left\{ \begin{array}{c} \frac{n(n-1)}{2}\ mod\ 3 = 0 \\ n\ mod\ 2 = 1 \end{array} \right.$ $=$ $\left\{ \begin{gathered} \left[ \begin{gathered} n\ mod\ 3 = 0 \\(n - 1)\ mod\ 3 = 0 \end{gathered} \right. \\n\ mod\ 2 = 1\\ \end{gathered} \right.$ $=$ $\left\{ \begin{gathered} \left[ \begin{gathered} n\ mod\ 3 = 0 \hfill \\ n\ mod\ 3 = 1 \hfill \\ \end{gathered} \right. \\n\ mod\ 2 = 1\\ \end{gathered} \right.$ $=$ $\left\{ \begin{array}{c} n\ mod\ 3 \neq 2 \\ n\ mod\ 2 = 1 \end{array} \right.$

Everything above proves the necessity of the conditions $n\ mod\ 3\ \neq\ 2$ and $n\ mod\ 2\ =\ 1$ to be true. Despite this, I have no idea how to prove the sufficiency. Thus, I would like to ask you to give me a hint.

By the way, I came across a theorem that contains the same condition but is related to a different topic, Planar graphs.

Theorem 3.1:

Let G be a graph embedded in the plane where the number of edges in the boundary of each face is a multiple of three. Then G is vertex colorable in three colors if every vertex has even degree.

A triangulation is a graph embedded in the plane in which the boundary of every face is a triangle (3-cycle); a triangulation is even if every vertex has even degree. (As we shall see, triangles are a recurring theme in 3-colorability.)

Quo Vadis, Graph Theory 1993. Chapter 21. The state of the three color problem.

• $n$ must also clearly be odd – Jorge Fernández Hidalgo Nov 3 '17 at 19:02
• Yes, it is one of the introduced conditions which are to be proved. – Radical Ed Nov 3 '17 at 19:10

## 1 Answer

Clearly we must have that each vertex has even degree and we must have that the number of edges is a multiple of $3$, so we must have $x\equiv 1$ or $3\bmod 6$.

The problem that you are trying to solve is usually known as the theorem on the existence of steiner triple systems.

Here is an explanation of the constructions.