Decidir T/F sobre la conectividad de vértices y aristas

Question

Decide, si es verdad, que:

$\forall $ gráfico $G$ : si $K(G) \neq \lambda(G) $ entonces $\exists $ vértice $v$ : $deg(v)\geq 4$ (donde $K(G)$ es la conectividad de los vértices y $\lambda (G)$ es la conectividad de los bordes)

Así que tengo 2 soluciones:

1, si lo niego de inmediato obtengo:

$ \exists G : K(v) = \lambda(G) : \forall v : deg(v) \leq 3 $ - lo cual es absolutamente cierto debido a $K_4$ - por lo que si la negación es verdadera, el problema original debería ser falso.

2, por contradicción digo que $\forall v : deg(v) \leq 3 $ mientras que $K(G) \neq \lambda(G)$ todavía se mantiene

por los grados podemos decir, que $K(G) \leq \lambda(G) \leq 3$ pero sé que $K(G) \neq \lambda(G)$ por lo que obtengo $K(G) < \lambda(G) \leq 3$ lo que parece una contradicción, pero no sé cómo demostrarlo. (por supuesto, eso significaría que la frase original es verdadera)

Se agradece cualquier ayuda.

Answer 1

Su negación de la afirmación es incorrecta. La negación correcta sería: Existe un gráfico $G$ para que $K(G) \neq \lambda(G)$ y el grado máximo de $G$ es como máximo 3. Recuerda que la negación de ( $p \Rightarrow q$ ) es ( $p$ y no $q$ ).

Su segunda estrategia es un buen comienzo. Usted sabe $K(G) < \lambda(G) \leq 3$ . Por lo tanto, $K(G) \in \{0,1,2\}$ . Si $K(G) = 0$ entonces $\lambda(G) = 0$ el gráfico ya está desconectado. Si $K(G) = 1$ hay un vértice $v \in V(G)$ para que la eliminación de $v$ desconecta el gráfico. Pero $\deg_G(v) \leq 3$ por lo que para algún componente de $G - v$ debe ser el caso que $v$ envía como máximo 1 arista $e$ a ese componente. Pero entonces $e$ es un borde de corte, y $\lambda=1$ . Si $K(G) = 2$ Se puede hacer algo similar - mira los vértices cortados, cada uno debe enviar como máximo 1 arista a uno de los componentes, y esas aristas juntas serían un corte de arista.

De hecho, se puede utilizar esta misma estrategia sin hacer el análisis de casos: basta con mirar cualquier conjunto de vértices cortados $V$ en el gráfico, siempre que el grado máximo sea como máximo 3, cada uno envía como máximo una arista a uno de los componentes de $G-V$ y ese conjunto de aristas sería un corte de aristas.