\documentclass{article}
\thispagestyle{empty}
\usepackage{tikz}
\def\nodeDist{2.5cm}
\tikzstyle{origVertex} = [draw, blue, fill, shape=circle]
\tikzstyle{newVertex} = [draw, red, fill, shape=circle]
\tikzstyle{invisibleVertex} = [shape=circle]
\tikzstyle{origEdge} = [blue]
\tikzstyle{newEdge} = [red, densely dashed]
\tikzstyle{invisibleEdge} = [draw opacity=0]
\begin{document}
\begin{tikzpicture}[node distance=\nodeDist,semithick]
\node[origVertex] (0) {};
\node[origVertex] (1) [right of=0] {};
\node[origVertex] (2) [above of=0] {};
\node[origVertex] (3) [above of=1] {};
\node[origVertex] (4) [above of=2] {};
\path (0) edge[origEdge, out=-45, in=-135] node[invisibleVertex] (m0) {} (1)
edge[origEdge, out= 45, in= 135] node[invisibleVertex] (m1) {} (1)
edge[origEdge] node[invisibleVertex] (m2) {} (2)
(1) edge[origEdge] node[invisibleVertex] (m3) {} (3)
(2) edge[origEdge] node[invisibleVertex] (m4) {} (3)
edge[origEdge] node[invisibleVertex] (m5) {} (4)
(3) edge[origEdge, out=125, in= 55, looseness=30] node[invisibleVertex] (m6) {} (3);
\path (m0) edge[invisibleEdge, out= 135, in=-135] (m1)
edge[invisibleEdge, out= 45, in= -45] (m1)
edge[invisibleEdge, out=-145, in=-135, looseness=1.7] (m2)
edge[invisibleEdge, out= -35, in= -45, looseness=1.7] (m3)
(m1) edge[invisibleEdge] (m2)
edge[invisibleEdge] (m3)
(m2) edge[invisibleEdge] (m4)
edge[invisibleEdge, out= 135, in=-135] (m5)
(m3) edge[invisibleEdge] (m4)
edge[invisibleEdge, out= 45, in= 15] (m6)
(m4) edge[invisibleEdge] (m5)
edge[invisibleEdge, out= 90, in= 165] (m6)
(m5) edge[invisibleEdge, out= 125, in= 55, looseness=30] (m5)
(m6) edge[invisibleEdge, out=-125, in= -55, looseness=15] (m6);
\end{tikzpicture}
\begin{tikzpicture}[node distance=\nodeDist,semithick]
\node[origVertex] (0) {};
\node[origVertex] (1) [right of=0] {};
\node[origVertex] (2) [above of=0] {};
\node[origVertex] (3) [above of=1] {};
\node[origVertex] (4) [above of=2] {};
\path (0) edge[origEdge, out=-45, in=-135] node[newVertex] (m0) {} (1)
edge[origEdge, out= 45, in= 135] node[newVertex] (m1) {} (1)
edge[origEdge] node[newVertex] (m2) {} (2)
(1) edge[origEdge] node[newVertex] (m3) {} (3)
(2) edge[origEdge] node[newVertex] (m4) {} (3)
edge[origEdge] node[newVertex] (m5) {} (4)
(3) edge[origEdge, out=125, in= 55, looseness=30] node[newVertex] (m6) {} (3);
\path (m0) edge[newEdge, out= 135, in=-135] (m1)
edge[newEdge, out= 45, in= -45] (m1)
edge[newEdge, out=-145, in=-135, looseness=1.7] (m2)
edge[newEdge, out= -35, in= -45, looseness=1.7] (m3)
(m1) edge[newEdge] (m2)
edge[newEdge] (m3)
(m2) edge[newEdge] (m4)
edge[newEdge, out= 135, in=-135] (m5)
(m3) edge[newEdge] (m4)
edge[newEdge, out= 45, in= 15] (m6)
(m4) edge[newEdge] (m5)
edge[newEdge, out= 90, in= 165] (m6)
(m5) edge[newEdge, out= 125, in= 55, looseness=30] (m5)
(m6) edge[newEdge, out=-125, in= -55, looseness=15] (m6);
\end{tikzpicture}
\begin{tikzpicture}[node distance=\nodeDist,semithick]
\node[invisibleVertex] (0) {};
\node[invisibleVertex] (1) [right of=0] {};
\node[invisibleVertex] (2) [above of=0] {};
\node[invisibleVertex] (3) [above of=1] {};
\node[invisibleVertex] (4) [above of=2] {};
\path (0) edge[invisibleEdge, out=-45, in=-135] node[newVertex] (m0) {} (1)
edge[invisibleEdge, out= 45, in= 135] node[newVertex] (m1) {} (1)
edge[invisibleEdge] node[newVertex] (m2) {} (2)
(1) edge[invisibleEdge] node[newVertex] (m3) {} (3)
(2) edge[invisibleEdge] node[newVertex] (m4) {} (3)
edge[invisibleEdge] node[newVertex] (m5) {} (4)
(3) edge[invisibleEdge, out=125, in= 55, looseness=30] node[newVertex] (m6) {} (3);
\path (m0) edge[newEdge, out= 135, in=-135] (m1)
edge[newEdge, out= 45, in= -45] (m1)
edge[newEdge, out=-145, in=-135, looseness=1.7] (m2)
edge[newEdge, out= -35, in= -45, looseness=1.7] (m3)
(m1) edge[newEdge] (m2)
edge[newEdge] (m3)
(m2) edge[newEdge] (m4)
edge[newEdge, out= 135, in=-135] (m5)
(m3) edge[newEdge] (m4)
edge[newEdge, out= 45, in= 15] (m6)
(m4) edge[newEdge] (m5)
edge[newEdge, out= 90, in= 165] (m6)
(m5) edge[newEdge, out= 125, in= 55, looseness=30] (m5)
(m6) edge[newEdge, out=-125, in= -55, looseness=15] (m6);
\end{tikzpicture}
\end{document}