Editing Cubic graph (section)

==Coloring and independent sets==
According to [[Brooks' theorem]] every connected cubic graph other than the [[complete graph]] ''K''<sub>4</sub> has a [[vertex coloring]] with at most three colors. Therefore, every connected cubic graph other than ''K''<sub>4</sub> has an [[independent set (graph theory)|independent set]] of at least ''n''/3 vertices, where ''n'' is the number of vertices in the graph: for instance, the largest color class in a 3-coloring has at least this many vertices.

According to [[Vizing's theorem]] every cubic graph needs either three or four colors for an [[edge coloring]]. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three [[perfect matching]]s. By [[Kőnig's theorem (graph theory)|Kőnig's line coloring theorem]] every bicubic graph has a Tait coloring.

The bridgeless cubic graphs that do not have a Tait coloring are known as [[Snark (graph theory)|snarks]]. They include the [[Petersen graph]], [[Tietze's graph]], the [[Blanuša snarks]], the [[flower snark]], the [[double-star snark]], the [[Szekeres snark]] and the [[Watkins snark]]. There is an infinite number of distinct snarks.<ref>{{citation
 | doi = 10.2307/2319844
 | last = Isaacs | first = R.
 | author-link=Rufus Isaacs (game theorist)
 | issue = 3
 | journal = [[American Mathematical Monthly]]
 | pages = 221–239
 | title = Infinite families of nontrivial trivalent graphs which are not Tait colorable
 | jstor = 2319844
 | volume = 82
 | year = 1975}}.</ref>