Having a hard time proving the last 2 questions of my homework. Will appreciate any clues.
$1$. Prove that any graph of minimal degree $d$ contains every tree of $d+1$ vertices.
This one seems quite easy, but I'm not sure whether my solution is right. I choose some way to traverse the vertices and adding them and the edges going out of them one-by-one (let's say by DFS). If failed in adding $v_i$, then there is no edge between some $v_j$, which I already added, to $v_i$ in the graph. But $v_j$ have at most $i-1
Is it right?
$2$. Set theory question need to be proved by graphs: Given $X$ - a $n$-element set and $n$ distinct subsets $A_1,...,A_n$, there exist $x \in X$ such that $A_1\cup\{x\},...,A_n\cup\{x\}$ are distinct as well. So the hint is to define a graph $G$ with vertex set $[n]$ and there is an edge between $i$ and $j$ if the symmetric difference between $A_i$ and $A_j$ is a single element $y$. We'll label the edge by $y$. Now, there is only left to prove, that there is a forest in $G$ contains exactly one edge with each label used.
Here I need some clues, at least to get me started.
Thanks in advance.