Prueba de teoría de grafos.

Question

1. Si G es conectado a un plano gráfico, entonces G tiene un vértice de grado en la mayoría de los 5.
2. Cualquier plano gráfico puede ser coloreado con 5/6 colores.
3. Cualquier árbol tiene al menos una hoja.

Soluciones: a Pesar de que he leído mucho sobre este tema estoy totalmente perplejos a los dos primeros. (Por favor, ayuda!)

Mi razonamiento para el tercero es la siguiente: a partir de cualquier vértice en el árbol y empezar a dibujar los bordes de la conexión de cada vértice a cualquier otro vértice. (Si no de la hoja, a continuación, cada vértice debe tener grado mayor o igual a 2.) Si tratamos de hacer de cada vértice tiene grado dos que vamos a llegar a un punto donde no podemos vértices de la izquierda y si tratamos de hacer un borde entre dos utiliza los vértices vamos a hacer un ciclo.

Answer 1

La primera afirmación puede demostrarse utilizando la fórmula de Euler: para un finito, conectado plano gráfico con $v$ vértices, $e$ bordes y $f$ caras, $v - e + f = 2$.

La segunda afirmación es el conocido cuatro-color teorema. Como señaló Johanna en los comentarios, parece poco probable que usted tenga que probar esto como un ejercicio.

La tercera demanda, puede ser demostrado mediante la aplicación de el hecho de que un árbol con $n$ vértices ha $n-1$ bordes.

---

Ps. Alternativamente, para la tercera demanda, podemos probar inductivamente el más fuerte afirmación de que cualquier árbol con dos o más vértices tiene al menos dos hojas.

Específicamente, nuestra hipótesis de inducción es que todos los árboles con $v$ vértices, donde $2 \le v \le n$, tiene al menos dos hojas. Claramente, este es vacuously cierto para $n=1$, por lo que podemos tomar como nuestro caso base.

Ahora, considere la posibilidad de un árbol con $v = n+1$ vértices, y observar que la eliminación de cualquiera de los bordes de este árbol te deja con dos más pequeños (pero no vacío) de los árboles. Si uno de estos pequeños árboles sólo tiene un vértice, entonces era una hoja en el árbol original; de lo contrario, por la hipótesis de inducción, cada uno de los árboles más pequeños debe tener al menos dos hojas, y unirse a otro árbol con un borde puede eliminar en la mayoría de los una de sus hojas. De cualquier manera, el combinado árbol heredará al menos una hoja de cada subárbol, y por lo tanto tiene al menos dos hojas.

(Tenga en cuenta también que esta fuerte demanda es tan fuerte que se puede obtener: para cualquier $n$, existe un $n$-vértice del árbol con exactamente dos hojas. Ejercicio: ¿qué tal un árbol?)

Answer 2

Deje $G$ ser simple, plana gráfico con $p$ vértices, $q$ bordes, y $r$ regiones.

Para la primera parte:

Deje $r_n$ el número de regiones delimitadas por $n$ bordes. Entonces

$$2q=r_1+2r_2+3r_3+\cdots+nr_n=3r_3+\cdots+nr_n\geq3(r_1+r_2+\cdots r_n)=3r$$

desde $G$ es sencilla (sin bucles o varios bordes significa que $r_1=r_2=0$). Por lo $r\leq 2q/3$. Ahora

$$2=p-q+r\leq p-q+2q/3=p-q/3$$ Así

$$q\leq3p-6$$

Si $N(G)$ da el conjunto de nodos en $G$, luego

$$\sum_{v\in N(G)}\text{deg }v=2q\leq6p-12$$

Así

$$\frac{\sum\text{deg }v}{p}\leq 6-\frac{12}{p}<6$$

A continuación, debe existir un vértice en $G$ con grado $5$.

Para la parte dos:

Usted sólo tiene que argumentar que cada subgrafo de un simple, plana gráfica es simple y plana para completar la prueba de la parte 2. Una vez que haya establecido que el hecho de que una simple inducción muestra que cada simple, plana gráfico es $5$degenerada, que es en la mayoría de las $6$-engañosa.

Answer 3

1) Supongamos que al contrario que todos los vértices tienen grado de, al menos, $6$ y el gráfico de $G$ es planar. Por el Apretón de manos Lema, hay, al menos, $3v$ bordes. Un corolario a la fórmula de Euler, tenemos $e \leq 3v - 6$, una contradicción. Y por lo que debe existir al menos un vértice de grado en la mayoría de las $5$.

2) voy a tener que pensar más en ello y editar si es necesario.

3) vamos a probar un lexema. Cualquier gráfico con $\delta(G) \geq 2$ (grado mínimo de $2$) tiene un ciclo. Así que por el Apretón de manos Lema, $\sum_{v \in V} d(v) \geq \sum_{v \in V} \delta(G) = 2V$, lo que implica que hay al menos $V$ bordes en $G$.

Por este lema, observamos que cualquier gráfico con un grado mínimo $2$ no puede ser un árbol, como un árbol ha $V-1$ bordes. Por lo tanto, debe ser una hoja (un vértice con grado de $1$).