demostrar que en un grafo orientado completo existe un triángulo

Question

Demostrar que en un grafo orientado completo existe un triángulo .

Intenté usar algo como bordes rojos y azules. Pero no puedo averiguar cómo elegir las direcciones de los bordes y de qué color es cada borde.

Answer 1

Si por "triángulo" se entiende un (dirigido) $3-$ ciclo, entonces esto es falso. Alinee el $n$ vértices de izquierda a derecha y hacer que cada arista sea una arista hacia delante (de izquierda a derecha). Este torneo claramente no tiene un $3-$ ciclo.

EDIT : Como @Brandon señaló en los comentarios, la afirmación es verdadera si el gráfico tiene al menos un ciclo.

Para verlo, supongamos que nos dan el ciclo $u_k\rightarrow u_{k+1}\rightarrow u_{k+2}\cdots \rightarrow u_{k+m}\rightarrow u_{k}$ , ordena los vértices del ciclo de izquierda a derecha (la última arista de la secuencia es una arista posterior).

Si tenemos un borde delantero $u_{k+1}\rightarrow u_{k+m}$ entonces hemos terminado, ya que tenemos el ciclo 3 $u_k\rightarrow u_{k+1}\rightarrow u_{k+m}\rightarrow u_k$ .

Si no, tenemos un ciclo más pequeño $u_{k+1}\rightarrow u_{k+2}\cdots \rightarrow u_{k+m}\rightarrow u_{k+1}$

Continuando con este razonamiento, también se puede ver que a menos que todas las aristas de $u_{k+m}$ a los vértices $u_{k+2}, u_{k+3}\cdots$ en el ciclo son aristas traseras, al final encontrarás un ciclo de 3. Pero si todos ellos son aristas posteriores, entonces tenemos lo siguiente $3-$ ciclo --

$u_{k+m-2}\rightarrow u_{k+m-1}\rightarrow u_{k+m}\rightarrow u_{k+m-2}$ .

Así que hemos terminado.

Answer 2

Lo probaré usando inducción.
Base: Para un gráfico de tamaño $3$ es verdad.
Hipótesis: Supongamos por tamaño $k$ es verdad.
Inducción: En gráfico de tamaño $k+1$ consideremos tres vértices consicutivos cualesquiera del ciclo. Sea $a, b, c$ tales vértices con orientación $(a-b-c)$ .
Caso 1: Si la arista $ac$ tiene orientación $(a-c)$ crea ciclo con $k-1$ vértices y según la hipótesis este ciclo contiene un triángulo.
Nota: Este ciclo no contiene $b$ . es decir $cycle-b$
Caso 2: Si la arista ac tiene orientación $(c-a)$ entonces $abc$ crea un triángulo.

Answer 3

Un grafo completo orientado (también conocido como torneo ) no contiene necesariamente un $3$ -pero los contraejemplos son muy especiales.

Suponga que su grafo completo orientado no contiene ningún grafo dirigido $3$ -ciclo. Para los vértices $a$ y $b$ define $a\lt b$ para significar que hay un arco desde $a$ a $b$ . Como el grafo es completo y no tiene direcciones $3$ -siempre que tengamos $a\lt b$ y $b\lt c$ también debemos tener $a\lt c$ . Es decir, $\lt$ es una relación transitiva, y por tanto es una relación de orden lineal, siendo obvias las demás propiedades requeridas.

Por lo tanto, los únicos grafos completos orientados sin $3$ -ciclos son órdenes lineales (a.k.a. torneos transitivos ), que no tienen ningún ciclo dirigido.