Límite para el tamaño de la gráfica con ciclos.

Question

Tengo el siguiente problema:

Deje que$G$ sea un gráfico simple con$n$ vértices y de manera tal que cada ciclo en$G$ tenga una longitud$\leq3$. Entonces $e(G)\leq\dfrac{3(n-1)}{2}$. (donde$e(G)$ es el número de bordes del gráfico$G$)

Creo que podría ser una buena idea probar esto por inducción, pero no sé cómo usar el límite para la duración de los ciclos.

Answer 1

Supongamos que la gráfica tiene 3 ciclos$C_1,C_2,...C_k$ y$\varepsilon$ bordes. Cada ciclo tiene 3 bordes y debido a la condición de que cada ciclo sea de longitud 3, cada borde tiene como máximo un ciclo de 3. Así que tenemos$$ k\leq {\varepsilon\over 3}$ $

Supongamos que el gráfico tiene el subárbol que abarca$T$ que tiene exactamente$n-1$ bordes. Entonces, cada borde que no esté en$T$ (tenemos$\varepsilon -n+1$ de esos) debe estar exactamente en un ciclo de 3. Pero no podemos tener más esos bordes que los 3 ciclos. Así que tenemos$$ \varepsilon -n+1\leq k \leq {\varepsilon\over 3} \Longrightarrow \varepsilon \leq {3n-3\over 2} $ $