Estoy confundido con una línea en la demostración de un teorema que forma parte de unos apuntes de Teoría de Grafos en los que estoy trabajando.
El enunciado del teorema es el siguiente:
$tw(G)=min\{\omega(H)-1:$ $H$ es una triangulación de $G$$\}$ , donde $tw(G)$ es la anchura del árbol de $G$ y $\omega(H)$ es el tamaño de una camarilla máxima en $H$ .
La prueba comienza demostrando la siguiente afirmación:
G es acorde (triangulado) si y sólo si tiene una descomposición en árbol en la que cada bolsa (parte) es una camarilla.
Esta parte de la prueba la entiendo. La prueba continúa como sigue:
Dejemos que $H$ sea una triangulación de $G$ . Desde $G$ es un subgrafo de $H$ cualquier descomposición en árbol de $H$ es también una descomposición en árbol de $G$ y por lo tanto $tw(G) \leq tw(H)$ . Dado que toda camarilla de $H$ está contenida en una de las bolsas de su árbol de descomposición, sabemos que $tw(H) \leq \omega(H)-1$ .
Y así sucesivamente...
Ahora entiendo que cualquier descomposición en árbol de $H$ es una descomposición en árbol de $G$ ya que lo probé como un ejercicio. Por lo tanto, entiendo que $tw(G) \leq tw(H)$ . También entiendo que cada camarilla de $H$ está contenida en una de las bolsas de su árbol de descomposición ya que también probé este resultado como ejercicio. Pero, ¿por qué eso implica que $tw(H) \leq \omega(H)-1$ ? Seguramente toda composición arbórea de $H$ debe tener una bolsa que contenga la mayor camarilla en $H$ por lo que la anchura de cualquier descomposición en árbol de $H$ debe ser como mínimo $\omega(H)-1$ y por lo tanto $tw(H) \geq \omega(H)-1$ ? ¿Me estoy perdiendo algo?
Muchas gracias
