# Arboricity Of Graphs

**ARBORICITY**: Any graph G can be expressed as a sum of spanning forests, simply by letting each factor contain only one of the q lines of G. A natural problem is to determine the minimum number of line-disjoint spanning forests into which G can be decomposed. This number is called the arboricity of G and is denoted by r (G).

**For example.** r (K4) = 2 and r (K5) = 3, minimal decompositions of those graphs into spanning forests are shown in Figure 7.6 below.

**Theorem .** For any nontrivial connected graph G,

**α0 β0 = P = α1 β1**

**Proof. **Let M0 be any maximum independent set of points, so that |M0| = β0. Since no line joins two points of M0, the remaining set of P – β0 points constitutes a point cover for G so that **α0 ≤ P – β0.**

On the other hand, if N0 is a minimum point cover for G, so the set V – N0 is independent. Hence, β0 ≥ P – α0, proving the first equation.

To obtain the second equality, we begin with an independent set M1 of β1 lines.

A line cover Y is then produced by taking the union of M1 and a set of lines one incident line for each point of G not covered by any line in M1.

Since **|M1| |Y| ≤ P and |Y| ≥ α1.** It follows that **α1 β1 ≤ P**.

In order to show the inequality in the other direction, let us consider a minimum line cover N1 of G.

Clearly, N1 cannot contain a line both of whose endpoints are incident with lines also in N1.

This implies that N1 is the sum of stars of G (considered as sets of lines).

If one line is selected from each of these stars, we obtain an independent set W of lines.

Now,** |N1| |W| = P and |W| ≤ β1.**

Thus, **∝1 β1 ≥ P,** completing the proof of the theorem. Corollary If P is an hereditary property of G, then

**α0 (P) β0 (P) = P.**