Centring without phantom spacing

Since the first line is actually the equation, I would go this way:

\documentclass{article}
\usepackage{amsmath,amssymb}

\begin{document}

\newcommand\+{\mkern2mu}
\newcommand{\graphG}{\mathcal{G}}
\newcommand{\graphH}{\mathcal{H}}
\newcommand{\setCA}{\mathbb{C}}
\newcommand{\setE}{\mathbb{E}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\vertices}[1]{V\!\left(#1\right)}
\newcommand{\edges}[1]{E\!\left(#1\right)}
\newcommand{\tuple}[1]{\left<\,#1\,\right>}
\newcommand{\card}[1]{\left|#1\right|}

\begin{gather}
\exists\+e \in \edges{\graphG},    \graphH = \tuple{\vertices{\graphG},\ \edges{\graphG} \setminus \set{e} },    \graphH \in \setCA \\
\begin{aligned}\notag
\textbf{where}\;\setCA &= \text{set of all circular-arc graphs} \\
\setE  &= \text{set of all empty graphs}
\end{aligned}
\end{gather} 

\end{document} 

Nasty trick of the day, split is really a two column array type of thing. So why not try \multicolumn. That actually works. Though It is not nice

\documentclass[a4paper]{memoir}
\usepackage{amsmath}
\begin{document}

\newcommand{\graphG}{\mathcal{G}}                                                  
\newcommand{\modelM}{\mathcal{M}}
\newcommand{\card}[1]{\left|#1\right|}  
\newcommand{\vertices}[1]{V\!\left(#1\right)} 
\newcommand\HideMe[1]{\multicolumn{2}{c}{$\displaystyle #1$}}

\begin{equation}                                                                   
\begin{split}                                                                      
\HideMe{\modelM \mapsto \graphG, x \le \card{\vertices{\graphG}} }  \\  
\textbf{where}\;x &= \text{number of maximal overlapping regions in $\modelM$}                    
\end{split}                                                                        
\end{equation} 

\end{document}

I'm surprised the simplest solution has not been given, that is, using gathered. The additions with \DeclarePairedDelimiter are only stylistical.

\documentclass{article}
\usepackage{amsmath,mathtools}

\newcommand{\graphG}{\mathcal{G}}
\newcommand{\modelM}{\mathcal{M}}
\DeclarePairedDelimiter{\card}{\lvert}{\rvert}
\DeclarePairedDelimiter{\parens}{(}{)}
\newcommand{\vertices}{V\parens}

\begin{document}

\begin{equation}
\begin{gathered}
\modelM \mapsto \graphG, x \le \card{\vertices{\graphG}} \\
\text{\textbf{where} $x={}$number of maximal overlapping regions in $\modelM$}
\end{gathered}
\end{equation}

\end{document}

Multiple clauses can use alignedat that allows for specifying accurately the spacing:

\documentclass{article}
\usepackage{amsmath,mathtools}

\newcommand{\graphG}{\mathcal{G}}
\newcommand{\modelM}{\mathcal{M}}
\DeclarePairedDelimiter{\card}{\lvert}{\rvert}
\DeclarePairedDelimiter{\parens}{(}{)}
\newcommand{\vertices}{V\parens}

\begin{document}

\begin{equation}
\begin{gathered}
\modelM \mapsto \graphG, x \le \card{\vertices{\graphG}} \\
\text{\textbf{where} $x={}$number of maximal overlapping regions in $\modelM$}
\end{gathered}
\end{equation}
And another
\begin{equation}
\begin{gathered}
\modelM \mapsto \graphG, x \le \card{\vertices{\graphG}} \\
\begin{alignedat}{2}
&\textbf{where } & x&=\text{number of maximal overlapping regions in $\modelM$}\\
&                & y&=\text{something else}
\end{alignedat}
\end{gathered}
\end{equation}

\end{document}