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

I live with four people, who thankfully don't spend much time on maths.se. We decided this year that we'd do a Secret Santa. We can represent the arrangement of who's buying for whom using a directed graph $G = (V,E)$. $V = \{\alpha,\beta,\gamma,\delta,\varepsilon\}$ is our vertex set, and $(u,v) \in E$ iff $u$ is buying a present for $v$. We decided to produce this graph by writing our names on bits of paper, shuffling them around, and each picking one out. If the name we draw is invalid, then we draw another piece of paper. Our validation rules were as follows:

• No participant shall buy for themselves - so $(v,v) \notin E$
• $\delta$ and $\varepsilon$ are a couple, who will be buying for each other separately from the secret santa. Rather than waste edges, they've decided to render each other invalid, so $(\delta,\varepsilon) \notin E$ and $(\varepsilon, \delta) \notin E$
• Each person buys for exactly one other person - so $deg_{in}(v) = deg_{out}(v) = 1$

I know who I bought for. Can I deduce the entire structure of the graph from this information?

I can reduce the graph to four possible structures, posted as a partial answer, which already gives me a pretty large amount of information. I don't think I can get any more information about the state of the graph simply from knowing who I'm buying for, but I have some information on the order in which names were drawn, and know that we never had to reshuffle.

Based on information provided by the draw, how would I find the probability of each of the possible Secret Santa arrangements?

Partial answer - the possible graphs of giving:

In these graphs, the nodes labelled $\delta/\varepsilon$ or $\varepsilon/\delta$ will take on different values, leading to four possible graphs. In both situations, $\alpha$ has the most natural information. Can more be gained from knowledge of the draw?

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.
• The draw is where I get a bit hung up, since I'm not yet convinced that I get no information from that. Suppose that when $\delta$ drew, there were 3 names left, and they didn't need to redraw. If $\delta$ and $\varepsilon$ were still in the bag, then the probability of redrawing would be $\frac{2}{3}$. If only one was present, the probability of redrawing would be $\frac{1}{3}$. Can I use the observation that they didn't redraw to gain further information about what the state of the name-bag was? Nov 18, 2013 at 21:43
• Nobody had to draw more than once, and I think the papers were drawn in the order $\alpha, \delta, \gamma, \beta, \varepsilon$. Nov 18, 2013 at 22:08
• $\delta$ has a $1/2$ chance of drawing $\gamma$ ignoring invalid draws. If $\delta$ draws $\gamma$, there is no chance of $\gamma$ redrawing, while in the other case there is a $1/3$ chance. $P(A|B)=\frac{P(A\cap B)}{P(B)}$, so probability of $\delta$ drawing $\gamma$ given $\gamma$ didn't redraw is $\frac{1/2}{5/6}=\frac{3}{5}$. So chances are $\delta$ drew $\gamma$. That also means $\epsilon$ drew $\alpha$. What $\gamma$ and $\beta$ drew are uncertain. Nov 18, 2013 at 22:38
• Note: the above assumes that $\gamma$ does not realize that drawing $\alpha$ would also require a redraw, since it is less obvious that this would be an invalid segment in the graph. Nov 18, 2013 at 22:42