Tikz package in tabularx, |c|X| |c|c|—I want a compact 2 column table with no borders

I am not sure, how the desired result looks like. Maybe something like that:

If you want to use |c|c| as column declaration fot the table, the environment enumerate must be used in a box like \parbox or minipage with a given width. Or you can use environment varwidth. Additionally I have used package enumitem to format the items in the enumeration.

\documentclass[12pt]{article}
\usepackage{tkz-graph}

\usepackage{varwidth}
\usepackage{enumitem}

\begin{document}
\begin{table}
  \centering
  \begin{tabular}{|c|c|}
  \hline
    \begin{tikzpicture}[baseline=(current bounding box.center),scale=2]
      \GraphInit[vstyle=Classic]
      \SetUpVertex[Lpos=-90]
      \tikzset{VertexStyle/.style = {shape=circle, fill=black, minimum size=3pt,inner sep=0pt}}
      \Vertex[x=0,y=0]{S$_0$}
      \Vertex[x=1,y=-.5]{dS$_0$}
      \Vertex[x=1,y=0]{mS$_0$}
      \Vertex[x=1,y=.5]{uS$_0$}
      \Vertex[x=0,y=-1]{t=0}
      \Vertex[x=1,y=-1]{t=1}
      \Edge[label = $\widetilde{p}_1$,color=red](S$_0$)(uS$_0$) 
      \Edges[label = $\widetilde{p}_2$,color=yellow](S$_0$,mS$_0$)
      \Edges[label = $\widetilde{p}_3$,color=green](S$_0$,dS$_0$)
      \Edges[label = $1+r$](t=0,t=1)
      \path(current bounding box.north)--++(0,2pt);% enlarge the height of the picture
    \end{tikzpicture}
  &
    \begin{varwidth}[c]{.6\linewidth}
      \begin{enumerate}[label={\Roman*.}]
          \item $m < d < 1+r < u$
          \item $d < m < 1+r < u$
          \item $d < 1+r < m < u$
          \item $d < 1+r < u < m$
       \end{enumerate}
     \end{varwidth}\\
  \hline
  \end{tabular}
\end{table}
\end{document}

There are two things that cause extra space: one is the initial space introduced by itemize which you can remove by \@minipagetrue. and the other one is the baseline option you have in the TikZ picture. For the borders remove | and \hlines.

And you don't need extra tabular inside the tabularx environment.

Here is a hand tweaked version :

\documentclass[12pt]{article}
\usepackage{tkz-berge,amsmath,amsthm,amssymb,amsfonts,tkz-graph,tabularx,enumerate}
\usepackage[margin=1in]{geometry} 
\usepackage[latin1]{inputenc}
%commands for the tree packages below
\usetikzlibrary{trees,fit,shapes,arrows,calc, patterns}

\begin{document}
  \begin{table}
  \centering
  \begin{tabularx}{\linewidth}{ |c|>{\csname @minipagetrue\endcsname}X| }
  \hline
    \begin{tikzpicture}[scale=2,baseline={([yshift=1.5cm]current bounding box.center)}]
        \GraphInit[vstyle=Classic]
        \SetUpVertex[Lpos=-90]
        \tikzset{VertexStyle/.style = {shape=circle, fill=black, minimum size=3pt,inner sep=0pt}}
            \Vertex[x=0,y=0]{S$_0$}
            \Vertex[x=1,y=-.5]{dS$_0$}
            \Vertex[x=1,y=0]{mS$_0$}
            \Vertex[x=1,y=.5]{uS$_0$}
            \Vertex[x=0,y=-1]{t=0}
            \Vertex[x=1,y=-1]{t=1}
                \Edge[label = $\widetilde{p}_1$,color=red](S$_0$)(uS$_0$) 
                \Edges[label = $\widetilde{p}_2$,color=yellow](S$_0$,mS$_0$)
                \Edges[label = $\widetilde{p}_3$,color=green](S$_0$,dS$_0$)
                \Edges[label = $1+r$](t=0,t=1)
        \end{tikzpicture}
  &    \begin{enumerate}[I]
        \item. $m < d < 1+r < u$
        \item. $d < m < 1+r < u$
        \item. $d < 1+r < m < u$
        \item. $d < 1+r < u < m$
     \end{enumerate}\\\hline
  \end{tabularx}
 \end{table}
\end{document}

I had a similar issue before. I my case I had some Tikz graphics within the table. I found that placing the Tikz figures as PDFs simplifies the problem a lot. Maybe you can also place the figure as a PDF.

Below is a sample that I have.

\documentclass[]{article}
\usepackage[a4paper]{geometry}
\usepackage{array}
\usepackage{amsmath}
\usepackage{upgreek}
\usepackage{caption}
\usepackage{graphicx}


\providecommand{\tabularnewline}{\\}
\captionsetup[table]{skip=10pt}
\setlength{\tabcolsep}{2pt}


\begin{document}
\begin{table}
    \centering{}\caption{\label{tab:SummMass}A Summary}
    \begin{tabular}{|>{\centering}m{6.2cm}|>{\centering}m{4cm}|>{\centering}m{4cm}|}
        \hline 
        \smallskip{}
        \textbf{Normalization Procedure} & \smallskip{}
        \textbf{Generalized Mass} & \smallskip{}
        \textbf{Effective Mass}\tabularnewline
        \hline 
        \noindent \includegraphics[width=6cm]
        {../Progress/EffMass/Paper/2017-05-20/figures/fig05a} &
        $\begin{aligned}\bar{m} &
        =\boldsymbol{\uppsi}^{\text{T}}\mathbf{M}\mathbf{\boldsymbol{\uppsi}}\\
        & =\sum_{j=1}^{n}\left(\psi_{j}\right)^{2}m_{j}
        \end{aligned}
        $ & $
        \begin{aligned}m_{i}^{\text{eff}} &
        =\frac{\bar{m}}{\left(\psi_{i}\right)^{2}}\end{aligned}
        $\tabularnewline
        \hline 
        \includegraphics[width=6cm]{../Progress/EffMass/Paper/2017-05-20/figures/fig05b} &
        $\begin{aligned}\bar{m}_{\text{D}} &
        =\boldsymbol{\uppsi}_{\text{D}}^{\text{T}}\mathbf{M}\mathbf{\boldsymbol{\uppsi}}_{\text{D}}\\
        & =\sum_{j=1}^{n}\left(\psi_{\text{D},j}\right)^{2}m_{j}
        \end{aligned}
        $ & $\begin{aligned}m_{i}^{\text{eff}} &
        =\frac{\bar{m}_{\text{D}}}{\left(\psi_{\text{D},i}\right)^{2}}\end{aligned}
        $\tabularnewline
        \hline 
    \end{tabular}
\end{table}
\end{document}