demostrar que un grafo conexo con $n$ vértices tiene al menos $n-1$ bordes

Question

Demuestre que todo grafo conexo con $n$ vértices tiene al menos $n 1$ bordes.

¿Cómo puedo demostrarlo? Conceptualmente, entiendo que el siguiente grafo tiene 3 vértices, y dos aristas:

a-----b-----c

con $a$ , $b$ y $c$ siendo vértices, y $\{a,b\}$ , $\{b,c\}$ siendo bordes.

¿Hay alguna forma de demostrarlo lógicamente?

--UPDATE--

¿Le parece correcto? Agradecería cualquier consejo sobre cómo mejorar esta prueba. Muchas gracias.

Answer 1

Pista: Sea $\Gamma$ sea un grafo conexo. Si $T \subset \Gamma$ es un subárbol maximal, entonces $|E(\Gamma)| \geq |E(T)|$ y $|V(\Gamma)|=|V(T)|$ . (Donde $E(\cdot)$ y $V(\cdot)$ es el conjunto de aristas y vértices respectivamente).

Answer 2

Considere cualquier vértice arbitrario de los n vértices, llámelo vértice A. Dado que el grafo es conexo, siempre existe al menos un camino simple (sin ciclos) desde el vértice A a todos los vértices (excluyendo A). Consideremos ahora dos caminos simples de A a B y de A a C. Si B no es igual que C, debe haber al menos una arista diferente en los dos caminos. Dado que existen al menos n-1 (ya que hay n-1 vértices excluyendo A) caminos, n-1 aristas deben ser

Answer 3

Aquí podemos utilizar Conjuntos Disjuntos. Estructura de datos de conjuntos disjuntos La estructura de datos Union-Find es muy popular en informática (detección de ciclos, etc.).

Los Conjuntos Disjuntos de Vértices son muy útiles para definir componentes conectados en un grafo. El número de conjuntos disjuntos (DS) es igual al número de componentes conectados. $v,u \in V$ son miembros del mismo DS si existe una ruta desde $u$ a $v$ .

Para construir DSs de un grafo, empezamos con $|V|$ Conjuntos con cada $v\in V$ que representa un DS. A continuación, añadimos la información de las aristas. Para cada $\{v,u\} \in E$ Nosotros encontrar los DS a los que $v$ y $u$ pertenecer y unión los dos conjuntos si se encuentran en DS diferentes. Por tanto, para cada arista existe $1$ o $0$ operación sindical.

En este caso, como el grafo es conexo, debemos tener un único DS al final. Para fusionar $|V|$ DSs a uno, debemos tener $|V|-1$ Operaciones sindicales. Por lo tanto, al menos $|V|-1$ se requieren bordes.

Generalización : Si un gráfico tiene $k$ componentes conectados, debemos tener $|V|-k$ operaciones sindicales. Por lo tanto, $|E| \geq |V|-k$ o $|E|+k \geq |V|$