  The problem of computing induced subgraphs that satisfy some specified
restrictions arises in various applications of graph algorithms and has been
well studied. In this paper, we consider the following Balanced Connected
Subgraph (shortly, BCS) problem. The input is a graph $G=(V,E)$, with each
vertex in the set $V$ having an assigned color, "red" or "blue". We seek a
maximum-cardinality subset $V'\subseteq V$ of vertices that is color-balanced
(having exactly $|V'|/2$ red nodes and $|V'|/2$ blue nodes), such that the
subgraph induced by the vertex set $V'$ in $G$ is connected. We show that the
BCS problem is NP-hard, even for bipartite graphs $G$ (with red/blue color
assignment not necessarily being a proper 2-coloring). Further, we consider
this problem for various classes of the input graph $G$, including, e.g.,
planar graphs, chordal graphs, trees, split graphs, bipartite graphs with a
proper red/blue $2$-coloring, and graphs with diameter $2$. For each of these
classes either we prove NP-hardness or design a polynomial time algorithm.
