Tagged Questions
0
votes
2answers
44 views
Prove there is a tree with $n$ vertices having degrees $d_1, d_2…d_n$
For $n ≥ 2$ suppose $d_1, d_2,....d_n$ are positive integers with sum $2n - 2$. Prove there is a tree with n vertices having degrees $d_1, d_2....d_n$. I'm at a loss on this one. I'm sure it's pretty ...
5
votes
2answers
141 views
Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?
My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
0
votes
1answer
101 views
M-ary tree problem
A full $m$-ary tree $T$ has 81 leaves and height 4
1) Give the upper and lower bounds for $m$
2) What is $m$ if T is also balanced?
[with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 ...
1
vote
0answers
47 views
How can I prove this property of a $d$-ary tree?
I have the following homework (algorithms lecture):
Every $d$-ary tree $G=(V,E)$ contains a vertex $v$ such that the size of the subtree with root $v$ is at least $\frac{1}{d+1} \vert V \vert$ and at ...
1
vote
1answer
35 views
If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.
If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set.
Give some clue please!
Thanks anyway!
1
vote
1answer
75 views
Prove equivalence of conditions for a tree
Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent.
$G$ is a tree.
Any two vertices in $G$ can be connected by a unique simple path.
$G$ is ...
3
votes
0answers
64 views
Recurrence relation induction [duplicate]
Possible Duplicate:
Solving the recurrence $t(n)=(t(n-1))^2 + 1$
Show that the number of binary trees of height less than or equal to $n$ is given by the recurrence
\begin{align*}
...
1
vote
1answer
720 views
Number of Trees with n Nodes
I am struggling with a question that asks the number of trees that exist with x nodes and max level z. During my research I found that the number of binary trees with x nodes can be obtained by ...
0
votes
1answer
229 views
Graph Theory - Spanning Trees
Consider a graph $G$ composed of two cycles which share an edge. $C_x$ is the cycle of length $x$ and $C_y$ is the cycle length $y$, for $x,y \ge 3$. (for example, if $x = 6$ and $y = 5$, then $C_x$ ...
2
votes
3answers
1k views
How to show that every connected graph has a spanning tree, working from the graph “down”
I am confused about how to approach this. It says:
Show that every connected graph has a spanning tree. It's possible to
find a proof that starts with the graph and works "down" towards the
...
2
votes
1answer
175 views
Proof involving a minimum weight spanning tree.
Please help with the following homework problem:
Let G be an undirected graph, $v: E\to R$ and $w: E\to R$ be two weight
functions on the edges of $G$. Let $z: E\to R$ be defined as the sum of ...
1
vote
3answers
85 views
Comparison trees
You have 60 coins. You know that 1 coin is either lighter or heavier than the other coins. How many comparisons are needed in a worst case scenario to discover which coin is the false one and ...
1
vote
2answers
357 views
Graph - Minimum spanning tree
I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$).
Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum ...
5
votes
3answers
480 views
How do you calculate the average length of a random binary tree?
Assuming that you start out with a root node, and decide with 50% probability whether or not to add two children nodes. If they do, repeat this process for them. How can you find the average length of ...
