Teorema de Nash-Williams

---

En la teoría de grafos , el Nash-Williams teorema es una empacadora árbol teorema que describe cuántos borde disjuntos árboles de expansión (y más generalmente bosques ) un gráfico puede tener:

Un gráfico G tiene t árboles de expansión disjuntos de bordes si f para cada partición donde hay al menos t ( k  - 1) bordes que se cruzan ( Tutte 1961, Nash-Williams 1961). ^[1]${\ textstyle V_ {1}, \ ldots, V_ {k} \ subconjunto V (G)}$${\ Displaystyle V_ {i} \ neq \ emptyset}$

Para este artículo, vamos a decir que tal un gráfico tiene arboricity  t o es t - arboric . (La definición real de arboricidad es ligeramente diferente y se aplica a los bosques en lugar de a los árboles).

Tanto NW como el teorema de Menger caracterizan cuando un gráfico tiene k trayectorias de borde disjunto entre dos vértices.

G se puede dividir en t bosques de bordes disjuntos si, para cada , el subgrafo inducido G [ U ] tiene tamaño .${\ Displaystyle U \ subconjunto V (G)}$ ${\ Displaystyle | G [U] | \ leq t (| U | -1)}$

En otras palabras, para cada subgrafo S =  G [ U ], tenemos . Es estricto porque hay un subgrafo S que satura la desigualdad (o de lo contrario podemos elegir una t más pequeña). Esto conduce a la siguiente fórmula${\ Displaystyle t \ geq \ lceil E (S) / (V (S) -1) \ rceil}$

---