Si $G$ es un árbol (un gráfico conectado sin ciclos) el rango de $B_G$ es exactamente $n-1$.

Question

Que $G$ ser un grafo con vértices de $n$, y que $B_G$ ser su matriz de incidencia. Muestran que:

Si $G$ es un árbol (un gráfico conectado sin ciclos) el rango de $B_G$ es exactamente $n-1$.

Trato de usar que un árbol tiene siempre un vértice de grado uno, pero no conseguirlo.

Answer 1

La declaración en este formulario puede ser un poco engañoso. En general, si $G$ es cualquier grafo conexo, entonces el rango de su matriz de incidencia es $n-1$. Para ver esto, mira las filas de $B_{G}$ como vectores con entradas de mod $2$. La suma de estos vectores es $0$ porque la suma es la suma de todas las columnas, y cada columna tiene sólo dos $1$ entradas. Esto da que los vectores no puede ser lineal independiente, por lo que el rango es $ \leq n-1$. Para $\geq n-1$, sólo ver lo que significa para el gráfico de estar conectado en términos de la incidencia de la matriz. Tomar las combinaciones lineales de cualquier $k$ vectores entre las filas y comprobar que las sumas pueden no ser $0$ .