Question
Transcribed Text
Discuss the growth of the function f(n) = 2VZlogn Polynomial? Superpolynomial? Exponential?
Explain and show work.
Same Question for f(n)=(logn)
Prove that a tree (i.e. undirected and acyclic graph) of size two or more must always have a
degree-one vertex.
Prove that a tree of size n has exactly n - 1 edges.
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
Answer1: We assume by contradiction that the tree has no vertex of degree 1.This would imply that tree is connected and has at least two vertices, since each vertex from the tree is of degree at least 2.This would imply that the tree has a cycle (the proof is below), which contradicts the provided hypothesis.
So it must have at least one vertex with degree 1.
Proof that any undirected finite graph with vertex degree minimum 2 has at least one cycle.
We can start from anywhere and follow the path through edges. We notice that every time we are able to continue, because each vertex has degree at least 2; this means that there will be an unused edge to can stop. In the case that we choose to return to a vertex where we have already been => we found a cycle. If the graph is finite, the situation which occurs is the following: we will run out of unused vertices and we’ll have to revisit some vertex....
By purchasing this solution you'll be able to access the following files:
Solution.docx.
Return to homework library