Minimum number of possible proper colorings

Question

Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.

For any graph with $2k-2$ edges such that it can be properly colored using $k$ colors. What is the minimum number of $k$-colorings of a graph with $2k-2$ edges, over all graphs that admit such a coloring?

For example, If we construct the graph as a matching with $2k-2$ edges, then the number of possible properly colored matchings is $k^{2k-2}$. Thus, $k^{2k-2}$ is an upper bound.

I guess the minimum number is more than $k!(k-2)!$; see an extremal graph as follows:

But how can I prove it?

Furthermore, what is the minimum number of $k$-colorings of a graph with $k+s$ edges $(0< s \le k-2)$, over all graphs that admit such a coloring? Is it more than $k!(k-2)_{s}$? (Write (k)_s for $k \cdot (k-1) \cdots (k-s+1)$)

Answer 1

Maybe we can firstly consider simple case for $s = 1$. The $k!(k-2)$ seems to be a low bounded.

Note that if consider graph with $m \le k$ edges such that it can be properly colored by $k$ colors, then it is clear that the minimum number is $(k)_m$ and extremal graph is a $m$-star.

Now, suppose that $G$ is extremel graph with $k+1$ edges and maximum degree $3 \ge d < k$. Then we divide the edges of $G$, leading to two graphs $G_1$,$G_2$, where $G_1$ is a graph consisting of $d$-star and one extrea edge, and $G_2 = G \setminus G_1$. Thus the number of coloring of $G_1$ is more than $(k)_d \cdot (k-2)$, and the number of coloring in $G_2$ is more than $(k)_{k+1 - (d+1)}$. Thus, the number of coloring in $G$ is moren that $(k)_d \cdot (k-2) \cdot (k-3)_{k+1-(d+1)} \ge k!\cdot (k-2)$. For $d < 3$ and $d=k$ is trivial.