Número máximo de bordes en un gráfico donde la longitud de cada ciclo es un múltiplo de 3

Question

Yo estoy haciendo un problema que pide para encontrar el máximo número de aristas de un grafo en $n$ vértices que tiene la propiedad de que cada ciclo de la longitud es un múltiplo de 3.

Yo era capaz de mostrar que si $G$ contiene un ciclo de $C$ ciclo $C$ no puede contener un acorde. La respuesta es $n-1$ +$\left\lfloor{\frac{(n-1)}{2}}\right\rfloor$ los bordes.

De proceder por inducción y asumió que el resultado es cierto para el grafo de n vértices. Entonces, si G tiene $n+1$ vértices, a continuación, he reducido el problema en tres casos:

1. Existe un vértice en G de grado 1 ( luego de la inducción nos lleva a casa)
2. $\delta(G)$ $\geq$$3$ donde $\delta(G)$ es el mínimo grado de $G$ (por la observación de que en este caso $G$ debe contener un ciclo con un acorde)
3. Cuando ninguno de los dos primeros casos se mantenga. Estoy atascado con este caso. Ayuda?

Answer 1

Primero una variante de su no-acorde lema. Considere la posibilidad de un gráfico arbitrario donde cada ciclo tiene una longitud múltiplo de $3$, y supongamos que $$ a_1 - a_2 - a_3 - \cdots - a_{3k} - a_1 $$ es un ciclo. Suponga que existe un camino $$ a_i - b_1 - b_2 - \cdots - b_m - a_j $$ que no contiene ninguna arista o vértice intermedio del ciclo. Entonces demostrar que $i\equiv j\pmod 3$.

---

Ahora supongamos $G$ es un múltiplo de 3-gráfico del ciclo de con $n$ nodos y una máxima cantidad de bordes. A continuación, voy a argumentar que $G$ no puede tener un ciclo simple $$ a_1 - a_2 - a_3 - \cdots - a_{3k} - a_1 $$ donde $k>1$. Es decir, si lo hace. entonces podemos colapso de un triángulo mediante la identificación de los nodos cuyos índices son congruentes modulo $3$. Después de este colapso, el gráfico aún satisface las múltiples-de-3 condición: Si dispone de un nuevo ciclo (aparte de los escombros del triángulo) que no estaba presente antes, luego de que el ciclo debe incluir uno de los escombros de los nodos, pero luego el anterior lema dice que no puede involucrar a más de uno de los nodos y corresponde a un ciclo de la gráfica original que incluye un múltiplo de $3$ bordes en los escombros del ciclo; por lo tanto no es un múltiplo de a $3$ los bordes de la izquierda en los escombros de la gráfica también.

El colapso reducido tanto el número de nodos y el número de bordes por $3(k-1)$, pero podemos organizar los en $k-1$ nuevos fragmentos de la forma

      O
     / \
<---O---O

y adjuntar cada uno de esos en algún lugar. Cada fragmento contribuye cuatro aristas, así que terminamos con más aristas de lo que habíamos pero el mismo número de nodos -- contradiciendo la suposición de que $G$ tenía un número máximo de aristas.

Así que ahora sabemos que $G$ debe ser un árbol de triángulos y solo los bordes. Y es fácilmente demostrado por inducción que un gráfico de la figura tiene en la mayoría de las $n-1+\lfloor\frac{n-1}2\rfloor$ bordes.

---

Por otro lado, es fácil ver que $n-1+\lfloor\frac{n-1}2\rfloor$ bordes puede lograrse, por tener un vértice tiene grado $n-1$ y la conexión de sus vecinos de dos en dos a $\lfloor\frac{n-1}2\rfloor$ triángulos que comparten una esquina (con una hoja de vértice izquierdo sobre si $n$ es incluso).

Answer 2

He aquí un lexema sin prueba: Vamos a $G$ ser simple sin título-$2$ vértices y no cortar los vértices. A continuación, cualquiera de $G$ es un ciclo de la gráfica o $G$ tiene un borde $(v_1, v_2)$ de tal forma que su eliminación todavía deja un gráfico con no cortar los vértices. Tenga en cuenta que este borde es el acorde de un ciclo en el $G$.

Hemos terminado si $G$ es simplemente un ciclo, así que supongo que no es. Nuestro objetivo es encontrar dos vértices adyacentes que ambos tienen un grado $2$. Mediante la eliminación de ellos, reducir el número de vértices por $2$ y el número de aristas por $3$, así que usted gana por inducción. Supongamos que por medio de la contradicción, que no hay ningún par de vértices.

Primero supongamos que $G$ no tiene ningún corte vértice. Deje $G'$ ser el cosimplification de $G$, es decir, la gráfica obtenida mediante la identificación de cada par de aristas acompañado por un grado-$2$ vértice. Hay una ventaja $(v_1, v_2)$ que se forma un acorde de un ciclo en $G'$. En $G$, esta ventaja debe ser subdividido para hacer una ruta de $P$, y debe ser subdividida sólo una vez o de lo contrario nos han adyacentes grado-$2$ vértices, por lo $|P| = 2$. Deje $C'_1$ $C'_2$ ser ciclos de $G'$ que sólo se cruzan en $(v_1, v_2)$ (su existencia es implícita por el lema), y deje $C_1$ $C_2$ ser sus correspondientes ciclos en $G$. A continuación, la inconexión de la unión de $C_1$ $C_2$ es un ciclo en $G$, pero tiene una longitud de

$$0 - 2|P| \equiv 2 \pmod 3$$

lo que se contradice con cada ciclo habiendo $0 \pmod 3$ bordes.

Si $G$ tiene un corte de vértices, a continuación, elija uno en el que la eliminación separa el gráfico en partes $K$ $J$ tal de que no hay bordes entre las $K$$J$, y el orden de $K$ es mínima. (En particular, no hay corte de los vértices dentro de $K$). A continuación, el mismo argumento por contradicción de arriba muestra que debe haber dos grados-$2$ vértices adyacentes el uno al otro dentro de $K$.