Columnas
Supongamos nueve soldaditos de plomo, representados por puntos, dispuestos en el campo de batalla –una hoja de papel- en formación militar de tres filas y tres columnas. Fijémonos en el que ocupa la posición central y, con un lápiz, tracemos un camino desde él a todos y cada uno de los restantes. Si los trazos son exactamente rectilíneos, la figura resultante es una especie de estrella de mar de ocho brazos, pues el camino es único, en este caso. Si el mismo trayecto lo hacemos a través de un arco de circunferencia, veremos inmediatamente que, al menos, disponemos de dos caminos para unir los puntos. El resultado es ahora una margarita de ocho pétalos. Si llamamos vértices a los puntos y aristas a los caminos entre dos puntos, se observa que la estrella se compone de 9 vértices y 8 aristas, mientras que en la margarita hay 9 vértices y 16 aristas.
Cada vez que entre dos puntos tengamos más de un camino, podremos construir otro trayecto cerrado, es decir, un nuevo camino que empieza y acaba en el mismo punto. En efecto, si se puede ir de P a Q a través de los caminos c y c´, entonces partiendo de P llegamos a Q a través de c, y regresamos a P recorriendo c´ en sentido contrario. Por tanto, el trayecto c seguido de – c´ nos proporciona un camino cerrado, también llamado ciclo o lazo. En este sentido, la margarita posee 8 lazos que empiezan y acaban en el punto central.
Llamemos ahora V al número de vértices y A al número de aristas y calculemos V-A. Esta diferencia es 1 para la estrella y -7 para la margarita. Cada vez que tengamos, en una hoja de papel, una configuración de puntos y segmentos tal como la de la estrella, los matemáticos acostumbramos a llamarle un grafo; mientras que el caso de la margarita, que posee lazos, se llama árbol. El número V-A, para cualquier grafo que usted pueda imaginar, siempre es igual a 1, es decir, esta cantidad es un invariante para los grafos. Para los árboles, es un fácil ejercicio comprobar que V-A siempre es igual a 1-n, siendo n el número de lazos del árbol. Por ejemplo, para la margarita V-A=1-8= -7, como ya habíamos calculado. Divertido ¿verdad? Este sencillo “juego” fue inventado por Euler, allá por 1736, para resolver el famoso “problema de los puentes de Koenisberg”.