Basics of digraphs

Question

I am having a hard time proving some theorems on digraphs. I tried answering these for days and nights but I cannot figure out the right answer/proofs. I need help on this.

Let $n$ be a positive integer and let $S_n$ be any set with $|S_n|=n$. Define $D_n = (V,A)$ to be the digraph with $V(D_n)=\mathcal{P}(S_n)$, the set of all subsets of $S_n$, where $(X,Y) \in A(D_n)$ if and only if $X$ contains $Y$ properly as a subset. ($\mathcal{P}$ is for power set).

1. Prove that $D_n$ has a unique source.
2. Prove that $D_n$ has a unique sink.
3. Find a necessary and sufficient condition for $D_n$ to have carrier vertices
4. Find a formula for the size of $D_n$ in terms of n.
5. Prove that $D_n$ has no circuit.

Thanks in advance!

Answer 1

HINTS

Here are some hints. Please post further questions as comments to this answer and I will be glad to guide you further.

1. A source means a vertex with only outgoing edges -- so you are looking for a subset of $S_n$ which contains all other subsets. Which is it, and can you show it is unique?
2. A sink means a vertex with only incoming edges -- so you are looking for a subset of $S_n$ which is contained by all other subsets. Which is it, and can you show it is unique?
3. What are carrier vertices? Can you translate this into a set property like I did for (1) and (2)?
4. Size of $D_n$ in terms of vertices and edges -- can you experiment with $n=1, 2, 3$ and post your results here, so we can see how you can generalize? In particular, clearly, $|V(D_n)| = |\mathcal{P}(S_n)|$ which should be very easy to compute, the edges will take some work, both easy proofs by induction once you know the answers.
5. What would a circuit in $D_n$ mean? Suppose $v_1 \to \ldots \to v_k \to v_1$ is a circuit in $D_n$. What does that mean in terms of sets? For starters, can you show that if $(X,Y) \in A(D_n)$ then $(Y,X)\not \in A(D_n)$?