Hay un par de ejercicios en mis notas de la conferencia en la teoría de grafos a la que soy incapaz de producir una respuesta. Dejando $X$ ser la clase de $(K_{1,3} ,K_{4})$libre de gráficos (gráficos contienen ni $K_{1,3}$ o $K_{4}$) y pide a los siguientes:
$\bullet$ Mostrar que cada una de las $n$-vértice bipartito gráfico en $X$ tiene más de $n$ bordes. Encontrar un $n$-vértice bipartito gráfico en $X$ $n$ bordes.
$\bullet$ Mostrar que cada una de las $n$-vértice comparabilidad gráfico en $X$ tiene más de $2n$ bordes. Encontrar un $n$-vértice comparabilidad gráfico en $X$ $2n$ bordes.
$\bullet$ Mostrar que cada una de las $n$-vértice de la gráfica de $X$ tiene más de $\frac{5n}{2}$ bordes. Encontrar un $n$-vértice de la gráfica de $X$ con más de $2n$ bordes.
Para el primer punto, relativo a la grafos bipartitos he argumentado que en cada vértice sólo puede tener un máximo grado de $2$, más si eran más de este vértice y su $3$ vecinos de admitir a un inducida $K_{1,3}$. Por lo tanto, para cualquier gráfico bipartito $G$$X$, tendríamos $|E(G)| \leq \frac{2 \cdot n}{2}$ contabilidad para el conteo de los bordes de dos veces, la producción de la respuesta. Un ejemplo de un gráfico con $n$ vértices sería cualquier ciclo con $n \geq 4$ como $C_{6}$.
Para el segundo punto, estoy completamente seguro de que la dirección en la que abordar el problema. Sé que un indirected gráfica es una comparabilidad gráfico si se admite transitivo orientación, pero estoy completamente atascado en la forma de aplicar esta estrategia. Este ejercicio fue en la sección sobre la teoría de Ramsey, así que me preguntaba si yo necesarios para implementar esta para cualquiera de los dos últimos problemas.
Ayuda apreciada como siempre, gracias!
