Conectividad de aristas en el gráfico

Question

Dejemos que $\lambda(G)$ sea la conectividad de los bordes.

¿Alguien puede ayudarme con estas dos afirmaciones si son ciertas y, si es así, por qué?

$$ \lambda(G) \geq \lambda(G - e) $$

$$ \lambda(G - v) \geq \lambda(G) - 1 $$

Creo que ambas cosas son ciertas, pero me cuesta probarlas.

EDITAR: La conectividad de las aristas se define como el tamaño del corte de arista más pequeño del gráfico

Answer 1

Por el Teorema de Menger, $\lambda(G)=k$ si y sólo si $k$ es el número máximo tal que, para cada par de vértices distintos $s,t$ Hay por lo menos $k$ borde-desunido $s$ - $t$ - caminos.

Si, para cada par de vértices distintos $s,t\in V(G-e)$ Hay por lo menos $k$ borde-desunido $s$ - $t$ -sendas en $G-e$ entonces también hay al menos $k$ borde-desunido $s$ - $t$ -sendas en $G$ para cada par de vértices distintos $s,t\in V(G)$ Por lo tanto, $\lambda(G)\geq\lambda(G-e)$ .

$\lambda(G-v)\geq\lambda(G)-1$ no se sostiene en general. Por ejemplo, $G=(V,E)$ con $V=\{v_1,\dots,v_5\}$ , $E=\{\{v_i,v_j\}\mid i\neq j, i,j\in\{1,2,3,4\}\}\cup\{\{v_1,v_5\}\}$ . En este caso, $\lambda(G)=1$ pero $\lambda(G-v_5)=3$ .