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
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse 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....
Return to homework library