A graph on irrationals where p is adjacent to q if p^q or q^p is rational. When I was in high school I learned about an elementary proof that there exist irrational numbers $p$ and $q$ such that $p^q$ is rational. Put $p = q = \sqrt{2}$; if $p^q$ is rational, we are done. Otherwise take $p = \sqrt{2}^\sqrt{2}$and $q = \sqrt{2}$.  
I am sure that by now much more is known about this phenomenon. Maybe the answer can be described in terms of graph theory. Define a graph $G$ on the positive irrationals. Two irrationals $p$ and $q$ are adjacent in $G$ if and only if at least one of the two powers $p^q$ or $q^p$ is a rational number that is not an integer power of another rational. A similar graph $G^*$ could be defined on the positive real numbers. I would like to know what can be said about $G$ and $G^*$. For instance, what is the cardinality of the edge set $E(G)\ ?$ What is the maximum degree of $G\ ?$
Suggestions for proper tagging are most welcome.
 A: The answers are that $|E(G)|=2^{\aleph_0}$ and that every vertex of $G$ has degree $\aleph_0$.  
Proof:
The positive real solutions to $x^y=2$ form a curve of cardinality $2^{\aleph_0}$, and at most $\aleph_0$ of these have $x$ or $y$ rational, so $|E(G)|=2^{\aleph_0}$.  (It cannot be larger, because this is also the number of pairs of vertices.)  
For $g \in G$ with $g>1$, the set of positive real numbers $x$ such that $g^x$ is a prime number contains at most one rational number since if there were two, then we would obtain an equation $p^q=p'$ with $p,p'$ distinct primes and $q$ rational, which is impossible by unique factorization.  Thus $g$ has infinite degree.  On the other hand, the degree of $g$ is at most countable since $g^x = q$ and $x^g=q$ have at most one solution $x$ each for each $q \in \mathbf{Q}$.  Finally, the same arguments apply when $g<1$, with reciprocals of primes in place of primes.
Remark: The same statements hold for $G^*$ except that one should exclude the vertex $1$.
