Prove a graph $(V,E)$ with $d$-maximal degree let $k=d/2+1$ can be decomposed as $V=V_1 \cup\cdots \cup V_k$ where each $V_i$ is a loopless graph

Question

I tried looking at a vertex v with the maximal degree, that is $d(v)=d$ and started looking at it's neighbours $$N(v):=\{u\mid (u,v) \in E\}$$ therefore $|N(v)|=d$, now between every two vertice $z,w\in N(v)$ Where are no cycle so you can devide the nieghbour group into $d/2$ subgroups, now I get stuck with the other $V-\{v\}-N(v)$ vertices and I was trying to somehow put then into these groups but got stuck. Help anyone?

Answer 1

I was thinking long and hard about it and I realised that induction can be applied: for n=3 It's obvious we have three vertice $ v_1 , v_2, v_3 $ Highest possible degree here could be 2 so: $ V_1=v_1 $ $V_2$={$v_2, v_3$}

Suppose that the claim is true for all m where m < n: Let'a look at our G=(V,E) where |V|=n. Take a vertex $ v\in V $ such v has the minimal degree so we know that d(v)<=d. If we now look at V-{v} this graph has m=n-1 vertices and still has maximal degree of d (we didn't delete the vertex with the maximal degree) therefore by induction where's a decomposition into k=d/2+1 disjoint vertice group. Now if the v we removed closes a cycle in each of $ V_1, V_2,..., V_k $ it must be that it has at least 2 edges going into each component whereby it has to have at least 2k edges meaning d(v)>2k-1=d+1 but we don't have that many edges (bouded by d edges max degree) so where exists a component $V_j$ such that v joined with it doesn't close a cycle, so none of the groups have a cycle and where is exactly k disjoint vertice groups as such.

Answer 2

You can use the Nash-Williams arboricity theorem (see here), in particular, for any subgraph $H \subseteq G$ we have

\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*} where $\displaystyle d_H = \max_{v \in V_H}\deg_H(v)$.

I hope this helps $\ddot\smile$

Answer 3

This shows what happens when we removed the minimal vertex and it had an edge touching the maximal degree: