La definición inductiva de los cógrafos establece que:
Otra definición afirma que: $$G \text{ is cograph } \iff G \text{ or } \overline{G} \text{ is not connected}$$
La cuestión es cómo estas dos definiciones son equivalentes, especialmente cómo la segunda definición implica la primera.
No son equivalentes. Por ejemplo, tomemos la unión disjunta de dos copias de $P_4$ (el camino en $4$ vértices). Esto satisface la segunda definición, ya que no está conectado.
Sin embargo, no satisface la primera definición: la única forma de construir $2P_4$ de cógrafos más pequeños sería si $P_4$ fuera un cógrafo, y $P_4$ no satisface o bien definición.
La primera es la definición estándar de cógrafo. Que yo sepa, la segunda definición no describe una clase interesante de grafos.
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.
