  A well-known theorem of Vizing states that if $G$ is a simple graph with
maximum degree $\Delta$, then the chromatic index $\chi'(G)$ of $G$ is $\Delta$
or $\Delta+1$. A graph $G$ is class 1 if $\chi'(G)=\Delta$, and class 2 if
$\chi'(G)=\Delta+1$; $G$ is $\Delta$-critical if it is connected, class 2 and
$\chi'(G-e)<\chi'(G)$ for every $e\in E(G)$. A long-standing conjecture of
Vizing from 1968 states that every $\Delta$-critical graph on $n$ vertices has
at least $(n(\Delta-1)+ 3)/2$ edges. We initiate the study of determining the
minimum number of edges of class 1 graphs $G$, in addition,
$\chi'(G+e)=\chi'(G)+1$ for every $e\in E(\overline{G})$. Such graphs have
intimate relation to $(P_3; k)$-co-critical graphs, where a non-complete graph
$G$ is $(P_3; k)$-co-critical if there exists a $k$-coloring of $E(G)$ such
that $G$ does not contain a monochromatic copy of $P_3$ but every $k$-coloring
of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $e\in
E(\overline{G})$. We use the bound on the size of the aforementioned class 1
graphs to study the minimum number of edges over all $(P_3; k)$-co-critical
graphs. We prove that if $G$ is a $(P_3; k)$-co-critical graph on $n\ge k+2$
vertices, then \[e(G)\ge {k \over 2}\left(n- \left\lceil {k \over 2}
\right\rceil - \varepsilon\right) + {\lceil k/2 \rceil+\varepsilon \choose
2},\] where $\varepsilon$ is the remainder of $n-\lceil k/2 \rceil $ when
divided by $2$. This bound is best possible for all $k \ge 1$ and $n \ge
\left\lceil {3k /2} \right\rceil +2$.
