Sea $G$ un grafo en $n$ vértices. Encuentra el número máximo posible de aristas si $G$ no tiene emparejamientos de tamaño $3$.
Además, ¿qué sucede con otros tamaños?
Pista:
Es fácil ver que el caso "mejor" (es decir, tener el máximo número de aristas) con la cantidad mínima posible de emparejamientos es cuando el grafo está completamente conectado. Ahora convéncete de que el grafo completamente conectado $K_5$ con $n = 5$, es decir, con $10$ aristas no tiene un emparejamiento con $3$ aristas
$\quad$
Editar:
Mi respuesta es solo un caso específico ($n = 5$). Para un $n$ general mayor o igual a $6$, deberás utilizar el resultado sugerido por el usuario W.R.P.S en el comentario anterior para $s = 3$. Da $\max\{10, 2n - 3\}$ como respuesta a tu pregunta.
Creo que todos podríamos haber descubierto por nosotros mismos el número máximo de aristas en un grafo simple con $5$ vértices sin coincidencias de tamaño $3$. ¿Cómo ayuda esto a determinar el número máximo de aristas en $n$ vértices sin coincidencias de tamaño $3$ cuando $n\gt5? ¿Se supone que sea obvio?
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.
1 votos
¿Tus pensamientos? ¿Coincidir tamaños 1 y 2 es fácil de manejar, verdad?
0 votos
Sí, para 2 creo que solo podemos tener una estrella, cae más o menos considerando casos. Pero para 3 se vuelve peor.
0 votos
Entonces, ¿qué sucede si consideras un borde y eliminas sus puntos finales del grafo?
1 votos
Sea $G=(V,E)$ un grafo con un conjunto de vértices $V = \{1,...,n\}$ y $4 \le 2s\le n$. Si $G$ no contiene ningún emparejamiento de tamaño $s$, entonces $ |E|\le \text{max}\{\binom{2s-1}{2},\binom{n}{2}-\binom{n-s+1}{2}\}$ prueba: La conjetura de Erdos sobre emparejamientos en hipergrafos-Katarzyna Mieczkowska-Teorema 8