Demuestre un gráfico$(V,E)$ con$d$ - grado máximo permita$k=d/2+1$ descomponerse como$V=V_1 \cup\cdots \cup V_k$, donde cada$V_i$% es un gráfico sin bucle

Question

Intenté mirar un vértice v con el grado máximo, que es$d(v)=d$ y comencé a mirar sus vecinos$$N(v):=\{u\mid (u,v) \in E\}$ $ por lo tanto$|N(v)|=d$, ahora entre cada dos vertice$z,w\in N(v)$ Donde están no hay ciclo, por lo que puedes dividir el grupo de usuarios en$d/2$ subgrupos, ahora me quedo con los otros$V-\{v\}-N(v)$ de vértices e intenté ponerlos de alguna manera en estos grupos pero me quedé atascado. Ayuda a alguien?

Answer 1

Puedes usar el teorema de arboricidad de Nash-Williams (ver aquí ), en particular, para cualquier subgráfico$H \subseteq G$ que tenemos

\begin{align*} \left\lceil\frac{|E_H|}{|V_H|-1}\right\rceil &= \left\lceil \frac{\frac{1}{2}\sum_{v \in V_H}\deg_H(v)}{|V_H|-1}\right\rceil \\ &\leq \left\lceil \frac{\frac{1}{2}d_H\big(|V_H|-1\big)+\frac{1}{2}d_H}{|V_H|-1}\right\rceil \\ &\leq \left\lceil \frac{1}{2}d_H + \frac{1}{2}\right\rceil &\leq k \end {align *} donde$\displaystyle d_H = \max_{v \in V_H}\deg_H(v)$.

Espero que esto ayude $\ddot\smile$

Answer 2

Yo estaba pensando mucho sobre eso y me di cuenta de que la inducción se puede aplicar: para n=3 Es evidente, que tenemos tres vértice $ v_1 , v_2, v_3 $ Grado más alto posible de aquí podría ser 2 por lo tanto: $ V_1=v_1 $ $V_2$={$v_2, v_3$}

Supongamos que la afirmación es verdadera para todos los m donde m < n: Vamos a buscar en nuestro G=(V,E) donde |V|=n. Tomar un vértice $ v\in V $ tal v tiene el grado mínimo, así que sabemos que d(v)<=d. Si ahora miramos V-{v} esta gráfica tiene m=n-1 vértices y todavía tiene el máximo grado de d (que no eliminar el vértice con grado máximo) por lo tanto, por inducción, donde una descomposición en k=d/2+1 discontinuo vértice grupo. Ahora bien, si la v nos quitan cierra un ciclo en cada una de las $ V_1, V_2,..., V_k $ debe ser que tiene al menos 2 de los bordes de entrar en cada componente de la cual ha de tener al menos 2k bordes significado d(v)>2k-1=d+1, pero no tenemos esa cantidad de bordes (bouded por d bordes grado máximo), así que donde existe un componente $V_j$ tal que v se unió con ella, no se cierra un ciclo, por lo que ninguno de los grupos tiene un ciclo y donde es exactamente k discontinuo vértice grupos como tales.

Answer 3

Esto muestra lo que ocurre cuando quitamos el vértice mínimo y tenía un borde tocando el grado máximo: