There is a graph with $N$ vertices and edges with $K$ distinct colors. No matter how one of these colors is chosen, if all the edges colored with this color is cut, the graph is edge-connected. The question is to find such colored graph with the least number of edges. I have an idea for this question, yet I don't know how to prove that my graph has the least number of edges. The following is my idea: For an arbitrary number of $K$, I first make cycles with $K$ distinct colors in touch with the center vertex as the following, and then the remaining vertices and the center vertex form a cycle which is a graph minor of other cycles. The following is the example of the case (N,K)=(11,4). Is there anyone who can prove this?

enter image description here


Of course $K\gt1$ is assumed, for the problem to make sense.

Your construction has $\lceil\frac{N-1}{K-1}\rceil$ cycles and $N-1+\lceil\frac{N-1}{K-1}\rceil=\lceil\frac{K(N-1)}{K-1}\rceil$ edges. This is best possible; for the given values of $N$ and $K$, any $N$-vertex graph with a satisfactory edge coloring must have at least that many edges. Namely, suppose the graph has $E_j$ edges of color $j$ for each $j\in\{1,\dots,K\}$, so that the total number of edges is $E=E_1+\cdots+E_K$. If we delete all the edges of color $j$, we are left with a connected graph having $N$ vertices and $E-E_j$ edges, whence $E-E_j\ge N-1$. Summing the $K$ inequalities obtained in this way, we get $(K-1)E\ge K(N-1)$, i.e., $E\ge\lceil\frac{K(N-1)}{K-1}\rceil$, Q.E.D.

  • $\begingroup$ I'm so amazed at what you easily answered this question, which I couldn't solve in spite of, at least, 3 hours of struggle with it. Thanks for your answer. It seems logically perfect to me. $\endgroup$ – Math.StackExchange Oct 3 '13 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.