Encontrar el más pequeño número $x$ para que si un grafo simple $n$-vértice tiene en por lo menos $x$ los bordes entonces contiene $k$ pares disjuntos por el borde perfecto lenceria * ($k$ es un número entero positivo, $n$ es un número par mayor que $k$).
* Significa encontrará conjuntos de $k$ que son pares disjuntos de borde.
Es bien conocido que el$K_n$, ${n \choose 2}$ bordes, se descompone en $n-1$ borde discontinuo perfecto elecciones. Considere la posibilidad de un gráfico de $G$, con al menos ${n - 1 \choose 2} + k$ bordes. $G$ que falta en la mayoría de las $n-1-k$ aristas del grafo completo, y cada falta borde significa que tenemos que tirar en la mayoría de los una de las perfectas elecciones. Por lo tanto, tenemos $n-1 - (n - 1 - k) = k$ borde discontinuo perfecto matchings a la izquierda.
Este es el mejor posible, ya que si tenemos un gráfico de $G$ eso $K_{n-1}$ con un adicional de vértice incidente a $k$ otros vértices, ha ${n-1 \choose 2} + k$ bordes y en la mayoría de las $k$ perfecto elecciones.
Esta es una respuesta para el caso $k=1$, tal vez usted puede construir en él. El ejemplo $K_{n-1}$ (más un vértice aislado) muestra que el $x > {n-1\choose 2}$. Supongamos ahora que $e(G) > {n-1\choose 2}$, así que el $e(G^c) < n-1$.
Para cada borde $e$ en el % de complemento $G^c$, hay $(n-3)!! = (n-3)(n-5)\cdots 1$ perfecto Lenceria de $K_n$ que pasan a través de $e$. Pero hay $(n-1)!!$ lenceria perfecta en conjunto y desde $(n-1)!! > (n-3)!! e(G^c)$, debe haber alguna coincidencia perfecta de $K_n$ que no contiene ningún borde de $G^c$, por lo tanto es un subgráfico de $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.
