  Given graphs $G, H_1, H_2$, we write $G \rightarrow ({H}_1, H_2)$ if every
\{red, blue\}-coloring of the edges of $G$ contains a red copy of $H_1$ or a
blue copy of $H_2$. A non-complete graph $G$ is $(H_1, H_2)$-co-critical if $G
\nrightarrow ({H}_1, H_2)$ and $G+e\rightarrow ({H}_1, H_2)$ for every edge $e$
in the complement of $G$. The notion of co-critical graphs was initiated by
Ne$\check{s}$et$\check{r}$il in 1986. Galluccio, Simonovits and Simonyi in 1992
proved that every $(K_3, K_3)$-co-critical graph on $n\ge6$ vertices has
minimum degree at least four, and the bound is sharp for all $n\ge 6$. In this
paper, we first extend the aforementioned result to all $(K_s,
K_t)$-co-critical graphs by showing that every $(K_s, K_t)$-co-critical graph
has minimum degree at least $2t+s-5$, where $t\ge s\ge 3$. We then prove that
every $(K_3, K_4)$-co-critical graph on $n\ge9$ vertices has minimum degree at
least seven, and the bound is sharp for all $n\ge 9$. This answers a question
of the third author in the positive for the case $s=3$ and $t=4$.
