Un instituto tiene 90 ex alumnos, cada uno de los cuales tiene diez amigos entre los demás ex alumnos. Demuestra que cada ex alumno puede invitar a comer a tres personas, de modo que cada una de las cuatro personas de la mesa del almuerzo conozca al menos a dos de las demás.
Sé que cada vértice tiene un grado 10 y que es un gráfico simple con el principio de encasillamiento trabajando de alguna manera. Cualquier ayuda sería apreciada.
Elige un vértice $v$ . Este vértice está conectado a $10$ otros vértices $v_1,..,v_{10}$ .
Hay 89 vértices diferentes de $v$ . Cada uno de los vértices $v_1,..,v_{10}$ está conectado a $9$ del otro $89$ vértices. Por lo tanto, hay 90 aristas que salen hacia el $V \setminus \{v\}$ .
Así, dos de las aristas que salen de $v_1,..,v_{10}$ tienen un vértice final común $w$ . Sea $v_iw$ y $v_jw$ sean estas dos aristas.
Ahora demuestre que si $v$ invita a $v_i, v_j, w$ resuelve el problema.
Elige un vértice cualquiera v. Está conectado a 10 vértices. Mantén estos 11 vértices a un lado. Nos quedan 79 vértices en el otro lado.
El caso central es cuando tenemos cinco pares disjuntos (es decir, cada par está formado por vértices distintos) de vértices conectados por aristas entre los 10 vértices a los que está conectado v. Por tanto, tenemos 5 triángulos en los que v es el único vértice común en cada uno de ellos.
Caso 1: si tenemos una arista extra entre dos vértices cualesquiera, podemos obtener un cuadrado o una figura similar a la de tener dos triángulos con base común, cualquiera de los cuales nos da el conjunto de cuatro vértices necesarios.
Caso 2: si no tenemos al menos 80 aristas (esta es la razón por la que lo llamé la configuración central. Actualmente hay 8 aristas por cada uno de los diez vértices a los que está conectado V. Si se resta una arista de aquí el no. 80 aumentará. Si me alejo de la idea de 5 pares distintos utilizando 5 o más aristas dentro de los 10 vértices a los que v está conectado, caeré en el caso 1.) que emana de nuestro conjunto de 11 vértices hacia el conjunto de 79 vértices. Por PHP, al menos 1 de los 79 vértices está conectado a dos de los diez vértices que dan lugar a un cuadrado.
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.
