# Questions in graph theory (tree embedding, set theory in graphs)

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<d$ neighbors (as it was the maximum number of vertices added by now). So it should have at least one more edge to still not existing vertex.

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.

-
This is a standard exercise in ordering vertices of a graph. I believe it's worked out in the beginning of Bollobas. –  Daniel Moskovich Nov 28 '11 at 20:35

Question 1: Your first question is a well known result due to Folklore and can be proved by greedily embedding vertices into the graph like you proposed.

Question 2: I asked an equivalent question to your second question a long time ago. It follows from Bondys theorem.

In future please only ask one question at a time to keep things simple.

-
Thanks for the answer. Regarding the second question, though, you didn't get a correct answer when using graph theory. The question was asked in a course 'Graph Theory', so I can't use set theory to prove this one (and it's only the first hw sheet, so there should be an elegant solution, not using any theorems). –  Pavel Nov 29 '11 at 6:50
Yes I saw such a proof once (cannot exactly remember the construction), but as in literature Bondys Theorem is never shown with graph theory I think that it is at least not better/much shorter than the other proofs. Maybe someone else can help out here :) –  Listing Nov 29 '11 at 7:39

Found an answer to that later. The "trick" is the following: if there's a cycle in graph, there must be at least two edges in it, labeled by the same $y$, because if we add an element to set, we'll need to subtract it later on.

After deleting one of those copies out of each cycle, we'll get what we need.

-