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?


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$

  • 1
    $\begingroup$ 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? $\endgroup$ – bof Dec 2 '18 at 11:55
  • $\begingroup$ 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 $\endgroup$ – rjm27trekkie Dec 2 '18 at 16:45
  • $\begingroup$ 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?) $\endgroup$ – bof Dec 3 '18 at 11:25
  • $\begingroup$ 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. $\endgroup$ – 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$).

  • $\begingroup$ 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 $\endgroup$ – rjm27trekkie Dec 3 '18 at 15:38
  • $\begingroup$ 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$. $\endgroup$ – theasianpianist Dec 3 '18 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.