¿Puede alguien afirmar o refutar la siguiente afirmación?
Reclamación:
En todo grafo no dirigido libre de triángulos $G=(V,E)$ , $|V|=7$ existe una arista $e\in E$ tal que $G'=(V,E\setminus\{e\})$ es bipartita.
Respuestas
¿Demasiados anuncios?
Dejemos que $G$ sea un gráfico sin triángulos con $|V(G)|=7$ y $|E(G)|>0$ . Si $G$ es bipartita, entonces $G \backslash e$ es bipartita para cualquier $e \in E(G)$ . Por lo tanto, asuma $G$ no es bipartita, y por tanto $G$ tiene un ciclo impar como subgrafo, que debe ser $C_5$ o $C_7$ ya que $G$ es libre de triángulos. Si $G$ no tiene $C_5$ subgrafo, entonces $G$ tiene $C_7$ como un subgrafo, pero cualquier cuerda de $C_7$ crearía un triángulo o $C_5$ Así que $G \cong C_7$ y $G \backslash e$ es bipartita para cualquier $e \in E(G)$ .
Ahora podemos suponer $G$ tiene $C_5$ como un subgrafo. Sea $V(G) = \{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}$ y asumir $C = v_1 v_2 v_3 v_4 v_5 v_1$ es un ciclo de 5 en $G$ . Cualquier acorde de $C$ crearía un triángulo, por lo que todas las aristas de $G$ no en $C$ están entre $v_6$ y $v_7$ o entre uno de $v_6$ o $v_7$ y $C$ . Obsérvese que ni $v_6$ ni $v_7$ puede ser adyacente a dos vértices adyacentes en $C$ ya que esto formaría un triángulo, por lo que cada uno es adyacente como máximo a 2 vértices de $C$ . Además, si $v_6 v_7 \in E(G)$ entonces $v_6$ y $v_7$ no pueden tener un vecino común ya que esto crearía un triángulo. Estas dos observaciones implican que $G$ es un subgrafo de uno de los siguientes:
Obsérvese que en cada caso, al eliminar la arista roja se crea un grafo bipartito.
heropup
Puntos
29437
SwDevMan81
Puntos
203
Asumo que esto es cierto y trato de demostrarlo.
Yo partiría del hecho de que
Un grafo es bipartito si y sólo si no contiene un ciclo impar.
Desde $G$ no contiene $C_3$ puede contener sólo $C_5$ y/o $C_7$ . Así que mi opinión es que el borde $e$ debe romper todos estos ciclos borrándolos del gráfico.
También puede ser útil que
Cualquier grafo no dirigido libre de triángulos con 7 vértices tiene como máximo 12 aristas - el máximo se alcanza sólo en el grafo bipartito completo $K_{3,4}$
(Puedo elaborar si esta idea es útil), que se puede utilizar para ver cuántos ciclos impar puede tener el gráfico.
Así que asumiendo a continuación que $G$ contiene un ciclo impar (si no, podemos elegir $e$ para ser cualquier borde), entonces $G$ no es bipartita, por lo que tiene como máximo 11 aristas. A continuación, si $G$ contiene $C_7$ pero no $C_5$ podemos elegir $e$ para ser cualquier arista en $C_7$ por lo que podemos suponer a continuación que $G$ contiene $C_7$ y $C_5$ que deben tener al menos una arista común (de lo contrario obtendremos 12 aristas en $G$ ). Si no hay más $C_5$ sur $G$ elegimos $e$ para ser un borde común. Si hay otro $C_5$ sur $G$ ...entonces... bueno, hay algunos casos que hay que analizar... ¿Puedes elegirlo desde aquí?
