I am stucked at this problem:
Let $G$ be the graph defined as the the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,...,n\}$.
($n>0$)
Determine how many edges are there in $G$ using a combinatorial argument.
(The result is a function of $n$)
Determine how many edges are there in $G$ using a graph theoretic argument by showing that $G$ is regular.
For $n=2$ we can see that there are $4$ edges in the Hasse diagram but I failed to find a general formula.
Thanks for any hint/help.
Solution for part 1
Every edge in the Hasse diagram goes from a set $S$ to a set $S \cup \{x\}$ with exactly one more element. So we can count how many edges come from each set.
A subset $S \subseteq \{1, 2, 3, \ldots, n\}$ of size $k$ is the initial point of exactly $(n-k)$ edges, because there are $n-k$ possible elements $x$ to add to get $S \cup \{x\}$.
Therefore the number we're looking for is \begin{align*} \sum_{k=0}^n [\text{# of subsets of size } k] \cdot (n-k) &= \sum_{k=0}^n (n-k) \binom{n}{k} \\ &= \sum_{k=0}^n (n-k) \frac{n!}{k!(n-k)!} \\ &= n\sum_{k=0}^{n-1} \frac{(n-1)!}{k!(n-k-1)!} \\ &= n \cdot 2^{n-1}. \end{align*}
Alternatively, we can get directly to this answer with the following reasoning: each edge in the Hasse diagram corresponds to adding some element $x$ to get from $S$ to $S \cup \{x\}$. Given $x$, there are $2^{n-1}$ possible subsets of $\{1, 2, 3, \ldots, n\} \setminus \{x\}$ that will have such an edges. So there are $n$ ways to choose $x$ and $2^{n-1}$ ways to choose $S$ given $x$, making the total number of edges $n \cdot 2^{n-1}$.
Hint for part 2
Given some subset $S$ of $\{1, 2, 3, \ldots, n\}$ of size $k$, we determined there are $n-k$ edges with initial point $S$, since there are $n-k$ possible elements we can add. How many edges have terminal point $S$? So how many edges are there total?
For a regular graph with every vertex of degree $d$, the total number of edges is given by $\frac{d |V|}{2}$.