[abnote]

El problema que tengo es el siguiente:
Sea \( G \) un grafo tal que \( G = C_3 \times F \), siendo \( F \) otro grafo desconocido, sabemos que la suma de los grados del complementario de \( G \) es \( 42 \). Encontrad un grafo \( F  \)que cumpla tal condición.

No se por donde empezar, con la suma de grados puedo obtener el numero de aristas de \( G^C \) pero a partir de ahí no se encontrar el numero de vértices de \( G \) ni de \( F \)

Gracias

[Luis Fuentes]

Hola

El problema que tengo es el siguiente:
Sea \( G \) un grafo tal que \( G = C_3 \times F \), siendo \( F \) otro grafo desconocido, sabemos que la suma de los grados del complementario de \( G \) es \( 42 \). Encontrad un grafo \( F  \)que cumpla tal condición.

No se por donde empezar, con la suma de grados puedo obtener el numero de aristas de \( G^C \) pero a partir de ahí no se encontrar el numero de vértices de \( G \) ni de \( F \)

Si \( F \) tiene \( v \) vértices y \( a \) aristas, el número de aristas de \( G \) es \( 3v+3a \).

Junto con las del grado complementario suman \( 3v+3a+21 \) suman el máximo número de aristas de un grafo de \( 3v \) vértices que son \( \binom{3v}{2} \).

¿Sabes concluir?.

Saludos.

[abnote]

Hola, gracias por responder.

No se concluir, una vez que tienes la expresión que me has indicado, primero no se como interpretarla y segundo aunque tengas una expresión para saber el número de aristas aun no se como encontrar el número de vértices.

Muchas gracias

[Luis Fuentes]

Hola

 Dime que parte no entiendes. Te lo numero para mayor comodidad a la hora de fijar la duda:

 1) \( C_3 \) es el grafo cíclico de orden \( 3 \), con tres aristas y res vértices.
 2) \( F \) es un grafo cualquiera. Llamamos \( v,a \) respectivamente al número de vértices y aristas.
 3) El número de vértices del grafo producto es \( 3\cdot v \) y el de aristas  \( 3v+3a \).
 4) Si \( G^c \) tiene suma de grados \( 42 \), entonces tiene la mitas de aristas \( 42/2=21 \).
 5) La suma de aristas de un grado y de su complementario es el número de aristas del grafo completo. El grafo completo de \( N \) vértices tiene \( \binom{N}{2} \) aristas.
 6) En nuestro caso entonces:

\(  3v+3a+21=\binom{3v}{2} \)

 7) Operando y simplificando:
 
\(  2v+2a+14=v(3v-1) \)
\(  2a=3v(v-1)-14 \)

 Basta que le des un valor a \( v\geq 3 \) y ya tienes el valor de \( a \).

 La solución no es única.

 El ejercicio sólo te pides que des un ejemplo.

Saludos.

[abnote]

Muchas gracias, lo que no entendía era como encontrar el numero de vértices y la expresión que habías puesto. Adjunto captura porque no se como ponerlo aquí.

[Luis Fuentes]

Hola

Muchas gracias, lo que no entendía era como encontrar el numero de vértices y la expresión que habías puesto. Adjunto captura porque no se como ponerlo aquí.

Se pone así:

[tex]\displaystlye\binom{N}{2}[/tex]  para obtener \( \displaystyle\binom{N}{2} \)

¿Ahora te quedó claro?

Simplemente ahí tenemos en cuenta que si hay \( N \) vértices el número máximo de aristas son las formas de unir cada par de vértices con una de ellas; habrá tantas como pares de vértices, es decir, combinaciones de \( N \) elementos tomados de \( 2 \) en \( 2 \).

Saludos.

[abnote]

Buenos días,

Ahora sí. Muchas gracias