# Questions tagged [trees]

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.

1,903 questions
Filter by
Sorted by
Tagged with
17 views

### Why is it that two labeled trees being identical is not the same as two isomorphic trees? [closed]

Why is it that two labeled trees being identical is not the same as two isomorphic trees? Couldn't you just say those two graphs are isomorphic? Maybe I am misunderstanding the definitions.
17 views

### About using Young tableaux to find non isomorphic trees on N vertices

In these days I dive in combinatorics to estimate the class of non isomorphic trees on N vertices. After a while I realized this sounds me really similar when using Young Tableaux on permutation ...
20 views

### Special Aronszajn tree actually has continuum cardinality?

Wikipedia gives the following construction of a special Aronszajn tree. Supposedly, this tree has $\aleph_1$ nodes, as each level and each branch is countable. However, it seems to me that this ...
• 4,760
11 views

### Prove or disprove: (a) If G is a graph of order n and size m with three cycles, then m ≥ n + 2. (b) There exist exactly two regular trees. [closed]

How to prove or disaprove: (a) If G is a graph of order n and size m with three cycles, then m ≥ n + 2. (b) There exist exactly two regular trees. Any help is appreciated.
22 views

### Graphs with average degree $t$ embed all trees with $t$ vertices

I want to prove the following: A simple graph with average degree at least $t$ contains all trees on $t$ vertices as a subgraph. I tried proving this by induction. I first showed that if a graph $G$ ...
100 views

### Proving the sum of length of a unique path in a tree is less than equal to $n$ choose $2$.

I am having trouble on trying to prove this statement using induction. Given a tree with $n$ vertices with $n \geq 2$. $x$ is a fixed vertex, for each $v$ in the vertex set, $d(v,x)$ is the length of ...
• 81
54 views

### Average Distance Between Two Nodes In An Unweighted Tree

Given a random unweighted tree with $n$ vertices, what would be an average minimal distance between two of its vertices? To put it in a more formal way, let's denote the set of all trees with $n$ ...
28 views

### Does a minimum spanning tree has the lowest maximum weights among all spanning trees? [closed]

Say that we have G, an undirected connected graph that has a positive weight for each edge. Let a spanning tree T be the minimum spanning tree (MST) for G, and we define the maximum weight (MW) of a ...
1 vote
26 views

### FUSF /neq WUSF, 3-regular Tree, effective Resistance

My professor gave an example of a 3-regular tree where the Wired Uniform Spanning Forest (WUSF) is not equal to the Free Uniform Spanning Forest (FUSF), but I'm having trouble understanding the ...
• 11
1 vote
33 views

### Fault Tolerant MST

Consider a graph $G=(V,E)$ and an MST of $G$. I am wondering how many edges I need to store, to make the MST tolerant to edge failures. If there is only one edge failure, I require at most $n-1$ edges ...
• 41
38 views

• 291
137 views

### How to calculate number of spanning trees of $K_5$ with extra vertex on one edge?

Here we have $K_5$ complete subgraph that gives $5^3 = 125$ spanning trees (using Cayley's formula). Adding one vertex to arbitrary edge, gives me this graph for example. Using Mathematica, it gives ...
• 291
1 vote
78 views

### Graphs with a given number of edges and vertices of degree $3$

Original problem: Let a $\Gamma$ be a set of all graph's G following rules: $V_G \subset \mathbb{N}$, $|E_G| = 303$ and $G$ has $151$ vertices of degree $3$. (Last condition means that G can have ...
• 65
56 views

### Proving that if G is a tree that relative to the source vertex s then BFS (G) = DFS (G) = G

I'm trying to prove that if G is a tree that relative to the source vertex s then BFS (G) = DFS (G) = G. I thought to assume the negative that BFS (G) = DFS (G) = T. G and T are not same, then there ...
1 vote
52 views

### De-contracting minimum spanning trees

I'm thinking about how to prove the following statement on Wikipedia. Assume an undirected graph with weights for each edge. If $T$ is a tree of MST edges, then we can contract $T$ into a single ...
• 172
23 views

### Proper definition of a full tree

When I've searched up online mostly I found the definition for full trees to be limited to a tree which has 0 or 2 children for each of it's nodes. Which is okay to understand but here is my dilemma. ...
17 views

### Deletion in AVL trees

assuming that one has to delete the root of an AVL tree. Does it matter which node replaces the root, say if it is the next smaller or next greater number than the root itself, as long as the AVL-...
• 431
81 views

### Is $n^{n-2}$ the number of trees on $[n]$ where the sum of degrees of vertices is $2n-2$?

I'm trying to count the number of trees on $[n]$ given that $d_1,d_2,\dots,d_n$ are positive integers with $\sum_{i=1}^{n}d_i=2n-2$ and for $i\in[n]$ $\deg(i)=d_i$. My thought process here is that ...
1 vote
35 views

### Trees and $K_{10}$

$(ii)$ Ignoring vertex labels, how many distinct trees are there with $5$ vertices? Draw each such tree, and justify your conclusion that there are no more. $(iii)$ Choose one of the trees that you ...
• 1,007
1 vote
41 views

### Can a graph have multiple distinct minimum spanning trees?

I have the following undirected graph which has multiple edges that have the same edge weights, the question is it possible to find more than one distinct minimum spanning tree for the following graph?...
• 21
81 views

• 1,776
1 vote