For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

learn more… | top users | synonyms

0
votes
2answers
23 views

an intuition for $\sum {\frac{(n-2)!}{k_1!k_2!…k_n!}}=n^{n-2}$

in studying about Graphs I've faced to the problem which says that the number of trees on n points is $n^{n-2}$. In the solution manual of the book the problem is reduced to the summation $\sum ...
0
votes
2answers
32 views

The Hand Shaking Lemma

In any graph G=(V,E) [the hand shaking lemma] $$ \sum_{v \in V} \deg(v) = 2 |E| $$ (original at http://i.stack.imgur.com/af4en.png) where |E| donetes the number of edges I alredy tried to count ...
0
votes
0answers
37 views

In code sequence of tree replace every 0 with two 0 and every 1 with two 1 will it be tree again?

So i have this question If yes, explain how the structure of this graph depends on the structure of the original subgraph. In not, give an example of such sequence. I just want to be sure if i'm right ...
0
votes
0answers
16 views

Proving the treewidth of a graph is the maximum treewidth of the connected components

We have a graph $G = (V,E)$ and $C$ is the set of connected components of G. I want to prove that $tw(G) \geq $ Max $tw(C)$ where tw is the treewidth. I know the out sketch of the proof is to take ...
0
votes
1answer
212 views

Find Minimal Spanning Tree Using Prim's Algorith

What will be the minimal spanning tree using Prim's Algorithm for this graph Also can i draw a tree and assign the weights as i like,will there be a minimal spanning tree for such a graph
7
votes
2answers
2k views

Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: ...
0
votes
1answer
29 views

Why does no minimal spanning tree contain the longest edge of a circuit?

Let $G=(V,E)$ be a graph with lengthfunction $l:E\rightarrow\mathbb{R}$. How do I prove that if $e$ is a line in a circuit $C$ such that $l(e)>l(f)$ for all $f\in C$ with $f\neq e$, then we get ...
1
vote
1answer
30 views

prooving graph with no cycles and |V | = |E| + 1 is a tree.

My assignment is to prove that G = (V, E) is a tree if and only if |V | = |E| + 1 and G has no cycles. However, I am having some trouble doing just that. We defined a tree as a graph which is ...
1
vote
1answer
81 views

Finding connected components of the graph [duplicate]

suppose that I have the following undirected graph with the following adjacency matrix showing if there is an edge between the nodes: \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 ...
0
votes
0answers
179 views

DFS tree of a $K_{1,3}$-free connected graph

Let there be $G=(V,E)$ a connected, $K_{1,3}$-free graph. (A $K_{1,3}$-free graph is a graph which has no 'claw' structures in it, where a claw structure refers to a vertex that has $3$ edges ...
0
votes
1answer
17 views

Structual induction on mirror(mirror t) = t

I have to prove that for all binary trees $t$ the following property holds: $$mirror(mirror(t))=t$$ $mirror(t)$ is defined as: $$mirror(t) =\begin{cases} Empty, & \text{if $t$ is Empty} \\ ...
0
votes
2answers
41 views

Find a minimum spanning tree using Prim's algorithm

I have the adjacency matrix: Where we have nodes a to g, and with their respective weights x means symmetry, and the spaces left out are positive infinity $$\begin{array}{c|c|c|c|c|c|c|c|} & ...
0
votes
0answers
27 views

Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
-1
votes
1answer
136 views

Prove that at least one edge of minimum weight is in the minimum spanning tree of a graph.

Let G be a connected graph with edge weights w. Suppose T is a minimum spanning tree of G. Let X be any nonempty proper subset V(G). Prove that at least one edge of minimum weight in the cut induced ...
1
vote
1answer
86 views

Build Tree by Prüfer Code $(6,2,2,6,2,5,10,9,9)$

I have the Prufer Code $(6,2,2,6,2,5,10,9,9)$. I want to build the corresponding tree. My algorithm: 1) Tree = $\{\}$, code = $(6,2,2,6,2,5,10,9,9)$, count = $(1,2,3,4,5,6,7,8,9,10,11)$ 2) Tree ...
0
votes
0answers
34 views

Name for a Type of Tree Diagram (Simplified Family Tree)

I just want to know what the name for this type of tree diagram is. In order to be clear, I want terminology like "binary tree" or something like that (but a name which actually applies). If I ...
0
votes
1answer
22 views

finding heap child and partents

I did anwer the question but I'm not sure if this is right. can you guys double check my answer and let me know if its wrong. Question 1: For the heap element at position i in the underlying array of ...
1
vote
0answers
55 views

Graph Theory: Are Infinite Trees Planar?

Graph theory: Are infinite trees planar? I think countable trees are, but not uncountably infinite trees, apparently. How does one construct such a tree?
1
vote
3answers
50 views

Finding element in binary min-heap

I am trying to answer two questions. Can some one check my answer and let me know if its correct or not? Question 1: Which locations in a binary min-heap of n elements could possibly contain the ...
1
vote
2answers
60 views

How to prove that a connected graph with $|V| -1= |E|$ is a tree?

I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree. Could somebody please provide an argument to establish ...
1
vote
1answer
22 views

Upperbound in the number of spanning trees of a r-regular Graph

i was trying to proof this upper bound in the number of spanning trees $t(G)$ of an r-regular graph G (and discuss what happens with equality) $t(G)$ $\leq$ $\frac{1}{n}$$(\frac{rn}{n-1})^{n-1}$ ...
1
vote
1answer
24 views

Interpreting a nonstandard definition of a tree

Definition: A tree is a triple $(T,\sigma,\pi)$ where $T$ is a set and $\sigma$ is a so-called successor function from $T$ to the set $T^*$ of all nonempty subsets of $T$, together with a surjective ...
0
votes
2answers
114 views

Calculating the average degree/valency of vertices

If I were to let T be a tree with n vertices, what would be the average degree/valency of the vertices in T? How would I go about calculating this?
0
votes
1answer
24 views

Why is the spanning tree algorithm used for bridge-routing?

In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed ...
0
votes
0answers
13 views

time complexity of a tree dynamic programming problem

The original problem: http://codeforces.com/blog/entry/20508 581F — Zublicanes and Mumocrates, I want to prove that the time complexity is $O(n^2)$. Suppose we have a tree, how to prove that ...
2
votes
0answers
118 views

Bounding the global intersection of a family of sets

Suppose that we have a decision tree of height $r + 1$ that describes how to increment an $n$-bit integer in the range $[0, 2^n -1]$. That is, the internal nodes are labelled with a bit position that ...
1
vote
0answers
46 views

Completeness in M-ary trees where the value of M is variable.

Definitions of complete trees are typically limited to some specific kind of tree, often an $m$-ary tree, where the number of children each internal node must have is a positive integer $m$. Consider ...
0
votes
1answer
48 views

Why is tree not uniquely possible with given preorder and postorder traversal?

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? preorder and postorder inorder and postorder ...
1
vote
1answer
33 views

Prove that minimum spanning tree is a tree

From the the Wikipedia page Minimum spanning tree: A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total ...
0
votes
0answers
53 views

constructing directed graphs using leaves of a non-isomorphic directed binary trees

I have a simple binary tree with 4 leaves: a / \ b c / \ / \ 0 1 2 3 I want to find an algorithm that constructs all directed graphs using the tree ...
0
votes
0answers
13 views

Minimum(maximum) cost of a weighted uni-height tree

If we have a rooted tree with all trunks the same height, and every vertex assigned a weight, is there a simple method to find the route from root to a leaf with minimum(maximum) cost?
0
votes
1answer
86 views

Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8

Question: Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8 (in that order) into an (initially) empty binary search tree. Show also ...
1
vote
1answer
22 views

Set of edges not contained in any spanning tree

The question is as follows: Prove that in a graph $G$ a set of edges $X$ which is not contained in any spanning tree is a cycle (or possibly an edge disjoint union of cycles). My thoughts: Proceed by ...
0
votes
1answer
31 views

Minimum spanning tree edge count

Given is a weighted complete graph where every weigth is a positive ineger. Let n be the amount of vertices. I have to prove that the number of edges of a minimum spanning tree of that graph is equal ...
-1
votes
1answer
120 views

Number of paths from root to a node in a tree

How to prove inductively the total number of paths from the root to all leaves in a given tree? From what I understand, one should show how to find the number of paths to a specific leaf, then use ...
11
votes
0answers
161 views

Free medial magmas

A medial magma is a set $M$ with a binary operation $*$ satisfying $(a*b)*(c*d) = (a*c)*(b*d)$. Medial magmas constitute an algebraic category $\mathsf{Med}$, therefore there is a functor ...
1
vote
1answer
42 views

Finding Minimum Weight Subgraph Spanning Tree

Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1. Suppose we also have a subset ...
0
votes
1answer
25 views

Balance factor changes after local rotations in AVL tree

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: ...
0
votes
1answer
54 views

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree.

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree. I think i've done this right but i'm not sure.
4
votes
5answers
44k views

The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.

I am confused with this statement The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$. How come this is true. Lets say I have the following tree ...
0
votes
2answers
75 views

Tree. Number of nodes and children

Suppose a given tree $T$ has $n_1$ nodes that have $1$ child, $n_2$ nodes that have $2$ children, . . . , $n_m$ nodes that have $m$ children and no node has more than $m$ children, how many nodes have ...
1
vote
1answer
283 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 ...
1
vote
1answer
27 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
0
votes
1answer
19 views

Remove the root from a binomial tree

I have a binomial tree with height k. How do I proof that when I remove the root, the result will be k new binomial trees, each with with a height from 0 to k-1. Thanks in advance.
1
vote
1answer
119 views

Spanning trees of ladder graphs…

a. Draw the 1-ladder, 2-ladder, and 3-ladder graphs, and calculate the number of spanning trees for each. - I have completed this part and wanted to confirm that these numbers look accurate, I feel ...
2
votes
0answers
25 views

Maximum number of subtree in a spanning tree

Is it possible to determine the theoretical maximum of number of subtree that can be extracted from a spanning tree? Some context (I don't know whether this is useful): I build the spanning tree by ...
0
votes
0answers
44 views

Bottleneck distances for the Steiner problem in graphs

I have been reading the paper "Preprocessing the Steiner Problem in Graphs" by Duin (http://link.springer.com/chapter/10.1007%2F978-1-4757-3171-2_10) and I am having a bit of trouble wrapping my head ...
1
vote
2answers
71 views

Number of reachable vertices in a tree

Given a tree $T$ with infinite nodes. Each node of the tree has exactly $C$ children. I need to figure out that, starting from a node at distance $h$ from root, how many distinct vertices can be ...
0
votes
0answers
8 views

Tree decomposition (Citation needed)

Recently, I read the statement "Fix $k\geq 1$, Any tree with at least $k$ edges may be decomposed as a union of edge-disjoint subtrees, each having between $k$ and $3k$ edges" Now I was wondering ...