Here is the main idea. We partition the vertices $ V$ of $ G$ into two groups $ V_1$ and $ V_2$ so that the corresponding induced graphs $ G_1,G_2$ on $ V_1$ and $ V_2$ are connected and both $ |V_1|$ and $ |V_2|$ are even. Then we apply induction, and a bit adjusting finishes the job. We proceed by induction and prove a slightly stronger claim that $ k-m\ge \left\lfloor |V|/2\right\rfloor$ where we assume $ |V|$ may be also odd. Note that if we have proven the claim for a graph with even number of vertices $ |V|,$ it follows it's true for a graph with $ |V|+1$ vertices. Indeed, we take a vertex $ v$ that leaves the graph still connected upon removing it. This is possible, for example, taking a leaf of its spanning tree. Then we color appropriately the vertices of the remaining graph and finally choose a color for $ v$ that does not decrease $ k-m.$ In case $ n=1$ (that is, $ |V|=2)$ the statement is trivial. Suppose we have a connected graph $ G(V,E)$ with $ |V|$ even, $ |V|>2,$ and we have proven the claim for all graphs with vertices less than $ |V|.$ There exists a vertex $ v_0\in V$ with degree at least $ 2.$ Otherwise $ G$ would be disconnected. Take $ v_0$ as a root and construct a spanning tree of $ G$ via breadth-first-search (BFS) algorithm so that in the resulting spanning tree $ T,$ the degree of $ v_0$ is $ \ell:=\deg_G(v_0)\ge 2.$ Let $ v_0$ be connected with $ v_1,v_2,\dots,v_{\ell}.$ Denote by $ \Gamma_1,\Gamma_2,\dots,\Gamma_{\ell}$ the induced graphs on the subtrees with roots $ v_1,v_2,\dots,v_{\ell}$ (fig. 1). There are two possible cases: 1) Some $ \Gamma_i$ has even number of vertices; 2) Each $ \Gamma_i, i=1,2,\dots, \ell$ has odd number of vertices. Case 1) Say, $ \Gamma_1$ has even number of vertices. We group the vertices as in fig. 2, that is, we set $ G_1:=\Gamma_1$ and $ G_2$ be the induced graph on the remaining vertices. Let $ V_1$ and $ V_2$ be the vertex sets of $ G_1$ and $ G_2$ respectively. Both $ n_1:=|V_1|, n_2:=|V_2|$ are even. Let's color the vertices of $ G_1$ and $ G_2$ such that $ k_1-m_1\ge n_1/2$ and $ k_2-m_2\ge n_2/2.$ It's possible since $ G_1$ and $ G_2$ are connected and both have even number of vertices. (the induction hypothesis is used). Consider now the entire graph $ G$ with that coloring. We have $ k=k_1+k_2+k_c,$ where $ k_c$ denotes the number of cross edges between $ V_1$ and $ V_2$ with ends of different color. Accordingly, $ m=m_1+m_2+m_c,$ where $ m_c$ is the number of cross edges with equally colored ends. It yields \begin{align*} k-m&=k_1-m_1+k_2-m_2+k_c-m_c\\ &\ge (n_1+n_2)/2+k_c-m_c \end{align*} If $ k_c-m_c\ge 0$ we are done. In case $ k_c-m_c<0$ we flip the coloring of $ G_2.$ This does not affect $ k_1,m_1,k_2,m_2.$ What it affects is $ k_c-m_c$ and it changes its sign. Hence, the new coloring satisfies $$ \displaystyle k-m \ge (n_1+n_2)/2+k_c-m_c\ge (n_1+n_2)/2.$$ Case 2) All $ \Gamma_1, \Gamma_2,\dots, \Gamma_{\ell} $ have odd number of vertices. Assume first, there is an edge between some of them, say, between $ \Gamma_1$ and $ \Gamma_2.$ In this case we group the vertices of $ G$ as $ V_1:=V(\Gamma_1)\cup V(\Gamma_2)$ and let $ V_2$ be the set of remaining vertices. Since the induced graphs $ G_1$ on $ V_1$ and $ G_2$ on $ V_2$ are both connected, we proceed like above. Assume now, there is no edge (in $ G$) between any $ \Gamma_i, \Gamma_j, i\neq j.$ We color each $ \Gamma_i$ such that $$ \displaystyle k_i-m_i \ge \left\lfloor \frac{|V_i|}{2}\right\rfloor=\frac{|V_i|-1}{2}.$$ where $ V_i:=V(\Gamma_i).$ Let's choose the color of $ v_0$ arbitrary. Note that after flipping the color of all vertices of any $ \Gamma_i,$ the value $ k_i-m_i$ doesn't change. Since there are no edges between $ \Gamma_i$ and $ \Gamma_j\,,\, j\neq i,$ it only affects the edge $ v_0v_i.$ Thus, we can flip the color of each $ \Gamma_i$ (if needed) such that $ v_0$ and $ v_i$ be colored differently. It yields $$ \displaystyle k-m\ge \ell +\sum_{i=1}^{\ell} \frac{|V_i|-1}{2} =\sum_{i=1}^{\ell} \frac{|V_i|}{2}+\frac{\ell}{2}\ge \frac{|V|}{2}$$ since $ \ell\ge 2.$ Remark. More details and comments on other possible approaches (the probabilistic one) can be found in my blog.

This is such a nice problem . We prove the stronger statement that for any graph on $n$ vertices, $k - m \geq \left \lfloor\frac{n}{2}\right \rfloor$. We proceed with induction on $n$, the base case $n=2$ is trivial and now we look at a graph $G$ with $n + 1$ vertices. We say a graph is coloured ambiently if the colouring satisfies our problem condition. Case I: $n+1$ is odd. In this case, by the induction hypothesis, we now colour $G' = G - \{v_{n+1}\}$ ambiently and if $v_{n+1}$ is connected to more red vertices in $N_{G} (v_{n+1})$, then colour $v_{n+1}$ blue else colour it red and clearly $k - m \geq 0$, so we are done. $\blacksquare$ Case II: $n+1$ is even. In this case, if $v_{n+1}$ has odd degree, we are done by the procedure in Case I. If $v_{n+1}$ has even degree, then it must have an equal number of vertices of each colour in $N_{G} (v_{n+1})$. Now construct the spanning tree by taking $v_{n+1}$ as the root and vertices in $N_{G} (v_{n+1})$ as the vertices in the first level of depth. We have an even number of disjoint trees $G_1, G_2, \dots, G_{2k}$ and there is a tree $G_i$ with an even number of vertices. Now consider the graphs $G_i$ and $H = G - G_i$, by our induction hypothesis, we can colour these graphs ambiently and thus, $$k_{G_i} - m_{G_i} \geq \frac{|V_{G_i}|}{2} \text{ and } k_{H} - m_{H} \geq \frac{|H|}{2}$$Combining them we get that, $$k_{G_i} + k_H - m_{G_i} - m_H \geq \frac{n}{2}$$Suppose $k_x$ and $m_x$ are the number of edges with vertices of different colour and the number of edges with vertices of the same colour in the intersection of the graphs $G_i$ and $H$. We want $k_x - m_x \geq 0$, now suppose $k_x - m_x < 0$, we can simply swap the colours of every vertex and we will have $k_x - m_x \geq 0$ and thus we are done. $\blacksquare$