¿Por qué $K(1,3)$ un subgrafo prohibido de un grafo lineal $G$ ?

Question

Mi profesor enseñó sobre subgrafos prohibidos en clase. " $H$ es un subgrafo prohibido de $G$ para una propiedad $P$ si $G$ tiene propiedad $P$ y $G$ no puede contener un subgrafo inducido isomorfo a $H$ "

Puso un ejemplo $K(1,3)$ es un subgrafo prohibido de un grafo lineal $G$ .

Intenté resolver por contradicción. $G$ es un gráfico lineal de $H$ que contiene $K(1,3)$ como un subgrafo inducido. Si $v$ es un vértice si el grado $3$ en $K(1,3)$ y $v_1$ , $v_2$ , $v_3$ son adyacentes a $v$ en $K(1,3)$ entonces la arista $e$ correspondiente a $v$ en $H$ es adyacente a las aristas $e_1$ , $e_2$ , $e_3$ correspondiente a los vértices $v_1$ , $v_2$ , $v_3$ .

Aquí es donde me atasco. ¿Puede alguien ayudarme? ¿Dónde me he equivocado? ¿Es correcto este planteamiento?

Answer 1

El vértice $v$ tiene grado $3$ porque venía de un borde, $\epsilon$ en $H$ que compartía un vértice con $3$ otros bordes. Una arista sólo tiene $2$ vértices. Esto significa (principio de encasillamiento) que $2$ de esos $3$ deben compartir uno de los extremos de $\epsilon$ por lo que en el gráfico lineal $G$ los vértices correspondientes a esas dos aristas de $H$ deben compartir una arista por haber compartido un punto final en $G$ . Así que el subgrafo inducido no es el bipartito $K(1,3)$ .

Answer 2

Brandon du Preez ha respondido realmente a la razón. Permítanme escribir en detalle aquí.

Supongamos que un gráfico lineal $L(G)$ contiene $K(1,3)$ como subgrafo inducido. Sea $v_1$ sea el vértice de grado $3$ en $K(1,3)$ . $v_2,v_3$ y $v_4$ son adyacentes a $v_1$ en $K(1,3)$ . Por la definición de grafos lineales, cada vértice $v_i$ de $L(G)$ corresponde a una arista de $G$ que puede expresarse como $e_i$ para $i\in \{1,2,3,4\}$ .

Tenga en cuenta que $v_1$ tiene tres vecinos en $L(G)$ que corresponden a las tres aristas adyacentes con $e_1$ en el gráfico original $G$ . Por el principio de casillero, al menos dos aristas (digamos $e_2,e_3$ .) inciden en uno de los extremos de $e_1$ . Entonces por la definición de gráficos lineales, $e_2$ es adyacente a $e_3$ en $L(G)$ . Esto contradice el hecho de que $K_{1,3}$ es un subgrafo inducido de $L(G)$ .

Editar cuando estaba editando, no me había respondido la puntera. Por favor, ignora mi respuesta ahora.