Teoría de grafos - No 3 ciclos - Grado máximo k.

Question

Me he encontrado este problema en uno de los trabajos de un curso de introducción a la teoría de grafos (no es un curso que estoy tomando, así que no estoy pidiendo a nadie a hacer mi tarea :p).

Supongamos que $G$ $p$ vértices, $q$ bordes, grado máximo $k$ y no hay ciclos de longitud $3$. Demostrar que $q \leq k(p-k)$

La manera en que yo pensaba que era empezar con el vértice con grado de $k$ y, a continuación, la razón sobre el número posible de vecinos que tenía y los vecinos de los vecinos, pero ya que no hay una estructura para el gráfico no podía pensar de una manera. Los punteros o sugerencias sería genial.

Answer 1

Suponemos, por supuesto, que$G$ es un gráfico simple ; de lo contrario la declaración es falsa. Elija un vértice$u$ del grado máximo y deje$U=V(G)\setminus N(u),$ para que$|N(u)|=k$ y$|U|=p-k.$ Ya que$G$ no tiene triángulos,$N(u)$ es independiente; es decir, cada borde de$G$ tiene al menos un punto final en$U.$ Para$v\in V,$ let$E_v$ denota el conjunto de bordes de$G$ incidente con$v.$ Entonces$$q=|E(G)|=\left|\bigcup_{v\in U}E_v\right|\le\sum_{v\in U}|E_v|=\sum_{v\in U}\operatorname d(v)\le\sum_{v\in U}k=k|U|=k(p-k).$ $

Answer 2

Supongamos $G$ es un gráfico que es el triángulo libre y $\Delta(G)=k$. Deje $v\in V(G)$ tal que $\operatorname{deg}(v)=k$ y considerar la posibilidad de $N_G(v).$

CASO I ($p-k\le k$): no puede ser cualquier arista entre dos vértices en $N_G(v)$, de lo contrario $G$ tendría un triángulo. Por lo $N_G(v)$ independiente es un conjunto de vértices cuyos bordes ir todos para el resto de $p-k$ vértices. Por lo tanto $G$ puede tener al menos $k(p-k)$ bordes. No puede ser de cualquiera de los bordes de la conexión de los vértices en $V(G)-N_G(v)$ otra forma un triángulo que estaría formado. Por lo tanto el máximo número de aristas es $k(p-k)$.

CASO II ($p-k>k$): no puede ser cualquier arista entre dos vértices en $N_G(v)$, de lo contrario $G$ tendría un triángulo. Por lo $N_G(v)$ independiente es un conjunto de vértices cuyos bordes se distribuyen entre el resto de los $p-k$ vértices. Por lo tanto $G$ puede tener al menos $k^2$ bordes. Ahora, para cada una de las $u\in N_G(v)$ hay al menos $p-2k>0$ vértices en $V(G)-N_G(v)$ que no están en $N_G(u)$ y podemos añadir estos bordes en $V(G)-N_G(v)$ sin crear triángulos. Por lo que podemos añadir, al menos, $k(p-2k)$ más de los bordes de la $G$, de modo que tenemos, al menos, $k^2+k(p-2k)=k(p-k)$ bordes en $G$. Si tratamos de añadir más los bordes de la $G$ vamos a formar un triángulo uniendo dos vértices en $N_G(u)$ algunos $u\in N_G(v)$ o uniendo dos vértices no en cualquier $N_G(u)$. Por lo tanto el máximo número de aristas es $k(p-k)$.

En cualquier caso, hemos terminado.