¿Cómo puedo demostrar que $G$ (un gráfico simple) que tiene un diámetro $2$ y $\Delta(G)=n-2$ tiene $m\geq 2n-4$ , donde $n$ es el número de vértices y $m$ es el número de aristas.
Esto no parece un problema muy difícil, no sé por qué pero me confunde mucho. Realmente me gustaría ver cómo se debe resolverlo (como estoy estudiando por mi cuenta la teoría de grafos creo que la mayoría de mis pruebas tienden a ser un poco ad hoc y desordenadas).
Dejemos que $v$ sea un vértice de grado $n - 2$ y que $w$ sea el único vértice no adyacente a $v$ . Cada vecino de $w$ también es vecino de $v$ . Desde $G$ tiene exactamente el diámetro $2$ , $w$ es adyacente a algún vecino de $v$ . Dejemos que $s = \deg(w)$ . Porque $G$ tiene un diámetro $2$ cada uno de los $n - 2 - s$ vecinos de $v$ que no son vecinos de $w$ debe ser adyacente a algún vecino de $w$ . Por lo tanto, hay un total de al menos $$(n - 2) + s + (n - 2 - s) = 2n - 4$$ bordes en $G$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
