Assume $e$ is any edge in a graph $R$ and $v$ is any vertex in a graph $R$.
- Show that $R-e$ is a Rado Graph if and only if $R$ is a Rado Graph.
- Show that $R-v$ is a Rado Graph if $R$ is a Rado Graph
Do these proofs look good?
For the removal of an edge $e$, the proof follows from considering the Rado property that $\forall$ 2 finite sets of vertices $V, W \in R$, $\exists$ a vertex $v$ that is connected by edges to every vertex in $V$ and not connected to any vertex in $W$.
Assume that $e$ was one of these edges joining a vertex $x \in V$ to a vertex $v \in (V \cup W) \backslash R$ satisfying the Rado property for the given $V, W$. I may also choose $V'$ and $W'$ to be sets s.t. $x \in W$ and $V' \cup W' = V \cup W$. Then still $\exists$ $v' \in (V \cup W) \backslash R$ satisfying the Rado property for the given $V', W' \in R$. Now, in the graph $R-e$, $v'$ will satisfy the Rado property for $V, W$, and $v$ will satisfy the Rado property for $V', W'$. The argument for the only if part of this condition is the same but consider adding an edge to the graph $R-e$. $\square$
If I remove a vertex $x$ from the graph $R$, I may well have first removed $deg(x)$ edges from $x$. The Rado property will hold under removal of $deg(x)$ edges from a vertex $x \in R$ by repeated application of (1). Now I want to remove $x$ which should cause no issue given that x could only be the vertex satisfying the Rado property for $R$ given $V=\phi$ and $W$ finite with $W \in R-v$, but $R$ was a Rado graph before removing all the edges from $v$ (which would have connected to some vertices possibly in $W$), so there is a vertex $v \neq x \in R$ that will satisfy the Rado property in this case. Thus, $R-v$ is necessarily Rado. $\square$