Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks in advance.

share|improve this question
1  
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
add comment

2 Answers 2

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.

share|improve this answer
    
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
add comment
up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.