What am I getting for Christmas? Secret Santa and Graph theory

Solution 1:

Since $\epsilon$ and $\delta$ are, for all intents and purposes, symmetric, there is no way of knowing which of the two is giving you a gift unless you ask one of them and they decide to disclose it to you since the person they are giving it to isn't you (I don't know how strict or confidential your Secret Santa is). But, on to probability:

You have a simple directed graph with 5 edges and 5 vertices that are not necessarily connected. Thus there are without any preconditions, ${20\choose 5}$ possible graphs. However, we know one of the edges (specifically $\alpha\to\beta$) and that two edges are impossible. Moreover, we know that $\beta$ must have degree $2$. The chance of $\beta\to\alpha$ is precluded by the fact that this would force $\epsilon\to\delta$ or vice-versa, while $\beta\to\gamma$ can't happen because then we would have $\delta\leftrightarrow\epsilon$. So we have a $\frac{1}{2}$ chance of $\beta\to\delta$ and $\epsilon$ each. Let $\beta\to X$, where $X\in\{\delta,\epsilon\}$. Then, with your restrictions, $X\to\alpha$ and $\gamma$ are the only possibilities, again with a $50/50$ chance of each. Whether $X$ maps to $\alpha$ or $\gamma$ uniquely determines the graph, as your depictions illustrate. All this is to say, each of the four graphs you present is equally likely assuming that your draw was random.