Por tanto, el posible perjuicio causado por estas importaciones sería, a lo sumo, insignificante.

Question

Deje $G=(V,E)$ gráfico. Supongamos que para cada subgrafo $G'=(V',E') , G' \subset G, |E'| \le 2|V'|$. Muestra que es posible dirigir G tal que cualquier outdegree sería más que 2.

Traté de demostrarlo por inducción. Me he dado cuenta de que el grado mínimo en cualquier subgrafo de G es en la mayoría de los 4. He intentado eliminar el vértice $v_0$ con el grado mínimo en un determinado subgrafo de la gráfica original, alegando que la gráfica de los restantes vértices puede ser dirigido como se requiere. ¿Cómo puedo incluir el vértice $v_0$ en el nuevo grafo dirigido de tal manera que cualquier outdegree estaría todavía en la mayoría de los 2? Gracias

Answer 1

Vamos a proceder a través de la inducción, sobre el número de aristas.

Tomar un gráfico de $G$ y quitar una arista $e$, supongamos que sus vértices son a$u$$v$. Por la hipótesis inductiva $G- e$ puede ser dirigida de manera que todos los grados se $2$ o menos. Si uno de los $u$ $v$ tiene out-grado menos de $2$ hemos terminado.

De lo contrario, considerar el conjunto $R$ de todos los vértices alcanzables desde $u$ o $v$ mediante la orientación de los bordes. Si hay un vértice $x\in R$ con grado $1$ o $0$ lo que ha hecho, simplemente tome el camino (que va de $u$ o $v$$x$) y la inversa de cada borde, esto deja a uno de $u$ o $v$ con grado de $1$.

Suponga ningún vértice en $R$ tiene out-grado menos de $2$. A continuación, el número de aristas en $G-e$ entre los vértices en $R$$2|R|$, la adición de vértice $e$ obtenemos $2|R|+1$ bordes, una contradicción.