From 6366f18037b2bee1899cece03bbcb736b1ff85e4 Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan.marinn@um.es>
Date: Thu, 28 Jan 2021 12:47:05 +0100
Subject: x

---
 graf/n5.lyx | 213 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 213 insertions(+)

(limited to 'graf')

diff --git a/graf/n5.lyx b/graf/n5.lyx
index d4c4f1b..d8fa808 100644
--- a/graf/n5.lyx
+++ b/graf/n5.lyx
@@ -240,6 +240,75 @@ En adelante el grafo a considerar será
 .
 \end_layout
 
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\chi(G)=0$
+\end_inset
+
+ si y sólo si 
+\begin_inset Formula $G$
+\end_inset
+
+ es vacío.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Si 
+\begin_inset Formula $\chi(G)=0$
+\end_inset
+
+, en particular existe 
+\begin_inset Formula $f:V\to\emptyset$
+\end_inset
+
+ y 
+\begin_inset Formula $V=\emptyset$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Si 
+\begin_inset Formula $V=\emptyset$
+\end_inset
+
+, 
+\begin_inset Formula $E=\emptyset$
+\end_inset
+
+ y 
+\begin_inset Formula $f:V\to\emptyset$
+\end_inset
+
+ es una 0-coloración.
+\end_layout
+
 \end_deeper
 \begin_layout Enumerate
 \begin_inset Formula $\chi(G)=1$
@@ -311,6 +380,146 @@ Claramente
 
 \end_deeper
 \begin_layout Enumerate
+\begin_inset Formula $\chi(G)=2$
+\end_inset
+
+ si y sólo si 
+\begin_inset Formula $G$
+\end_inset
+
+ es bipartito con algún eje.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+La partición 
+\begin_inset Formula $\{f^{-1}(0),f^{-1}(1)\}$
+\end_inset
+
+ de 
+\begin_inset Formula $V$
+\end_inset
+
+ cumple que eje une dos vértices en el mismo conjunto y por tanto todos
+ unen un vértice de uno con uno del otro.
+ Hay algún eje porque si no lo hubiera sería 
+\begin_inset Formula $\chi(G)=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sea 
+\begin_inset Formula $(A,B)$
+\end_inset
+
+ la partición, definimos 
+\begin_inset Formula $f(v):=0$
+\end_inset
+
+ para 
+\begin_inset Formula $v\in A$
+\end_inset
+
+ y 
+\begin_inset Formula $f(v):=1$
+\end_inset
+
+ para 
+\begin_inset Formula $v\in B$
+\end_inset
+
+.
+ Entonces 
+\begin_inset Formula $f$
+\end_inset
+
+ es una 2-coloración de 
+\begin_inset Formula $G$
+\end_inset
+
+, y como hay algún eje, 
+\begin_inset Formula $\chi(G)>1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Todo árbol no trivial es bipartito.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Se tiene 
+\begin_inset Formula $|V|\geq2$
+\end_inset
+
+ y, sea 
+\begin_inset Formula $n(v)$
+\end_inset
+
+ el nivel de un 
+\begin_inset Formula $v\in V$
+\end_inset
+
+, 
+\begin_inset Formula $f:V\to\{0,1\}$
+\end_inset
+
+ dada por 
+\begin_inset Formula $f(v):=[n(v)]_{2}$
+\end_inset
+
+ es una coloración de 
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Como 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene ejes, 
+\begin_inset Formula $\chi(G)>1$
+\end_inset
+
+ y 
+\begin_inset Formula $\chi(G)=2$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Sea 
 \begin_inset Note Note
 status open
 
@@ -321,6 +530,10 @@ status open
 \end_inset
 
 
+\begin_inset Formula $C_{n}:=(\{1,\dots,n\},\{\{$
+\end_inset
+
+
 \end_layout
 
 \end_body
-- 
cgit v1.2.3