We are given a graph in which there exists a cut vertex, v, in which G-v creates two components. Also the degrees of all the vertices in G are equal and equal to k, making it k-regular. We're then asked to prove that χ'(G) > k.
I know for one vertex, we'd need k different colors for all the edges coming towards it, and I think that since all those edges don't go directly to one vertex we can have more than k colors in general. Also if the graph is k regular and has a cut vertex couldn't that vertex be any vertex in the graph? In any case I'm not too sure how the information about the cut vertex would relate to the proof, which is kind of where I am stuck right now.
Best Answer
Let $G$ be a (finite) $k$-regular graph with a cut vertex $v$, and assume for a contradiction that $G$ admits a proper edge coloring with $k$ colors. Fix such a coloring; each vertex of $G$ is incident with one edge of each color. Without loss of generality, we assume that $G$ is connected.
Since $v$ is a cut vertex, $G-v$ has at least two connected components, $G_1$ and $G_2$; and $v$ is adjacent to a vertex $u_1$ in $G_1$ and a vertex $u_2$ in $G_2$. Without loss of generality we assume that the edge $u_1v$ is colored red and the edge $u_2v$ is colored blue.
Let $H$ be the spanning subgraph of $G_1$ consisting of the edges in $G_1$ which are colored red or blue. In $H$ the vertex $u_1$ has degree $1$ and all other vertices have degree $2$. But this is impossible in a finite graph.