# Show Rado Graphs Are Stable Under Edge and Vertex Removal

Assume $$e$$ is any edge in a graph $$R$$ and $$v$$ is any vertex in a graph $$R$$.

1. Show that $$R-e$$ is a Rado Graph if and only if $$R$$ is a Rado Graph.
2. Show that $$R-v$$ is a Rado Graph if $$R$$ is a Rado Graph

Do these proofs look good?

(1)

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$$

(2)

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$$

• Does it have to be that complicated? Don't we know that, if $V$ and $W$ are disjoint finite sets of vertices in the Rado graph, than there is not just one but an infinite number of vertices $x$ joined to everything in $V$ and nothing in $W$? And isn't it pretty clear than adding or subtracting an edge, or subtracting a vertex, can't spoil more than $1$ of those infinitely many $x$'s? – bof Dec 2 '18 at 11:55
• If we suppose that the Rado property is satisfied by more than one vertex for any 2 finite sets then yes, but the definition doesn't tell me i get 2, just at least 1. So yes, i should have to care about there possibly being only one vertex satisfying the property for given V and W – rjm27trekkie Dec 2 '18 at 16:45
• Then why don't you first prove as a lemma that you can find more than one vertex for given $V$ and $W$? (Hint: what if you take the first vertex $x$ that you got, add it to $V$, and use the Rado property again?) – bof Dec 3 '18 at 11:25
• By the way, I believe the usual definition of the Rado property says that there is a vertex $x$ such that $x$ is joined to every vertex in $V$ and to no vertex in $W$, and $x\notin W$. You left out the $x\notin W$ part. Your version works too, but makes slightly more work. You might start by proving that your version is equivalent to the usual one. – bof Dec 3 '18 at 11:28

I disagree with part of your first proof. A vertex $$v \in (V \cup W) \backslash R$$ makes no sense, since $$V$$ and $$W$$ are both subsets of R, thus $$(V \cup W) \backslash R = \phi$$. A definition of $$R \backslash (V \cup W)$$ makes more sense to me, especially given how you defined the Rado property (each vertex $$v$$ which fulfills the property for some $$V$$ and $$W$$ cannot be a member of either $$V$$ nor $$W$$).
• This is the definition. $V \subset R, W \subset R$ but $V \cup W \neq R$. They are not spanning subsets of $R$ because they are FINITE while $R$ is countably infinite. (V \cup W) | R describes all these vertices not in V or W (2 finite subsets of R) that are also in R (that's what the relative set complement under R (\ operator) means – rjm27trekkie Dec 3 '18 at 15:38
• en.wikipedia.org/wiki/Complement_(set_theory) I stand by the statement that $(V \cup W) \backslash R$ means all members of $V \cup W$ which are not in $R$. – theasianpianist Dec 3 '18 at 15:54