The graph which has the least edges while satisfying this property

Question

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?

Answer 1

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.