0
votes
1answer
30 views

Determining the total degree of a tree

At the start of the solution, I understand that any tree with four vertices has three edges. I don't understand the next statement: "Thus the total degree of a tree with four vertices must be 6." ...
0
votes
2answers
38 views

Finite trees and embedding in infinite regular trees.

Assume that you have a finite tree $T=(V,E)$, where $V$ and $E$ are the set of vertices and edges of $T$, respectively. Let $d_{max}$ be the maximum degree the some vertice(s) $v\in{V}$. Assume also ...
1
vote
1answer
23 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
-1
votes
1answer
27 views

How many different binary search trees can be made with three pieces of data? [closed]

This is for a discrete math course, not computer science.
0
votes
1answer
32 views

How do I construct a minimum spanning forest?

I realize that a minimum spanning forest in a weighted graph is a spanning forest with minimal weight. Does this mean that I construct it by turning all of the trees into spanning trees?
1
vote
1answer
38 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
0
votes
2answers
62 views

How many trees are in the spanning forest of a graph?

Spanning forest is defined by the following definition: A forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two ...
0
votes
1answer
29 views

Proving that a sub-graph of a tree is a tree

The proof that P ::== any sub-graph, G* of the tree G, is also a tree, involves proof by contradiction. We can suppose that the sub-graph has a cycle --> the whole graph has a cycle --> the whole ...
0
votes
1answer
19 views

Definition of a leaf in a tree

Across two different texts, I have seen two different definitions of a leaf 1) a leaf is a node in a tree with degree 1 2) a leaf is a node in a tree with no children The problem that I see with ...
1
vote
3answers
48 views

Why do the children of a node $n$ in a complete binary tree have indices $2n $ and $2n+1$?

The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$? For ...
0
votes
1answer
26 views

find an algorithm to find MST in linear time while each edge has the same weight

I have been disscussing this problem with a lot of my friends . However no solution has been found. let G= w is a weight function for each e in E w(e)=1 find MST of G in O(|V|+|E|) thanks
1
vote
1answer
40 views

Largest order of automorphism group on a rooted tree?

MacArthur, Sanchez-Garcia, and Anderson have used the ratio of the order of $|Aut(G)|$ and $n!$ (i.e., order of $S_n$) as a normalized measure of the symmetries present in a graph. I am working on ...
0
votes
1answer
57 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
1answer
32 views

How I can prove the one order homology of a tree is zero

When T is a tree and d1 is boundary operator fromC_1(T) to C_0(T) how to prove kernel of d1 is {0} I think acyclic is key point but i don't know next step.
3
votes
2answers
44 views

How many vertices does this tree have?

Suppose that $T$ is a tree. It has $e$ edges and $n$ vertices, and $\overline{T}$ has $10e$ edges. What is n? I think $n = 1$ is a solution, because $T$ can have no edges then, so $0=10*0$. A ...
3
votes
2answers
56 views

Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.

For $n\ge4$, let G be a simple n-vertex graph with at least $2n - 3$ edges. Prove >that G has two cycles of equal length. (West's Introduction to Graph Theory Q 2.1.42) I am trying to prove the ...
4
votes
1answer
61 views

Infinite sequence of trees that are not subgraphs to each other

This is from a set of exercises and I am stuck to this. Please, have in mind, that I want to understand how it's solved, I am not just looking for a solution. Define an infinite sequence of trees ...
0
votes
0answers
15 views

Can an arbitrary network of nodes be effectively visualized as a circular “treemap”?

We all know that a treemap is effective for visualizing hierarchical tree data (i.e. where there are only 1 to many relationships like in a computer file system): But how difficult algorithmically ...
0
votes
2answers
29 views

A tree $T$ with 50 end-vertices has an equal number of vertices of degree 2, 3, 4, and 5 but contains no vertices of degree greater than 5.

What should be the order of $T$? So I know a graph $G$ is a tree if every two vertices of G are connected by a unique path
0
votes
1answer
37 views

What's an efficient algorithm for walking to a minimum spanning tree?

Given a connected directed acyclic graph $G(V, E)$, is there an algorithm for changing a spanning tree to a minimum spanning tree through a series of edge swaps? We can use Prim's or Kruskal's ...
1
vote
1answer
33 views

Graph G with two Spanning Trees

Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$ ...
5
votes
1answer
52 views

Finding graphs with a given number of spanning trees

All of the graphs considered in this question are connected. We can find the number of spanning trees $t(G)$ of $G$ using Kirchhoff's matrix-tree theorem or the deletion-contraction method. I'm ...
1
vote
1answer
43 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
1
vote
0answers
45 views

Proof of existing path on Depth-First-Search spanning tree

Let $G$ be an undirected connected graph, and $T$ the directed spanning tree of $G$, which I got by performing a DFS on $G$. If $H$ is a complete subgraph of $G$, how can I proof that there a path in ...
1
vote
2answers
33 views

Proof that spanning trees can be converted into one another

Let $T_1$ and $T_2$ be two spanning trees of a graph $G$. Prove that if $e$ is an edge of $T_1$, there exists an edge $f$ in $T_2$ so $T_1-\{e\}+\{f\}$ also is a spanning tree. For $\{e\}\subset ...
0
votes
1answer
23 views

Finding the parent of a node in recombining binomial tree

I have posted an earlier question: Finding the child node in the recombining binomial tree. Now I would like to find the parent of a node in recombining tree. The tree looks like this: Now I need ...
1
vote
0answers
94 views

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time.

So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red ...
1
vote
1answer
35 views

The complement of spanning trees is covered by a union of cycles

Is it true that in any (connected) graph $G=(V,E)$, if $T$ is a spanning tree than its complement (edge-wise) may be covered by a union of disjoint cycles? Here's a non-complete attempt to prove this ...
2
votes
1answer
30 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
5
votes
3answers
47 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
1
vote
2answers
24 views

How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
2
votes
1answer
44 views

Counting problem (should use Cayley's formula)

How many trees above $V=\{1,2,3,4,5,6,7,8,9\}$ are there, such that $deg(4)=5$? I know I should use Cayley's formula somehow.
2
votes
1answer
281 views

How to draw all nonisomorphic trees with n vertices?

I have a textbook solution with little to no explanation (this is with n = 5): Could anyone explain how to "think" when solving this kind of a problem? (for example, drawing all non isomorphic ...
3
votes
1answer
91 views

A Graph as a Union of K forests.

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k. I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a ...
0
votes
2answers
42 views

Determining number of parent node on an n-tree.

I'm sorry if this is the wrong one, was unsure if this was computer science, programming, or mathematics related. I'm going with mathematics because it is semi-graph theory related. I have a tree ...
0
votes
1answer
40 views

How to prove this necessary and sufficient condition for tree in graph theory?

Let $0<d_1\leq\ldots\leq d_n$ be integers. Show that there exists a tree with degrees $d_1,\ldots,d_n$ if and only if $d_1+\ldots+d_n=2n-2$.
0
votes
1answer
56 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
3
votes
2answers
148 views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
0
votes
1answer
43 views

Non-Isomorph trees of a graph

Please consider this graph How many non-Isomorph trees with 4 vertex has this graph? Is there any formula that show number of non-Isomorph trees with $n$ vertices? thanks
0
votes
1answer
43 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
1
vote
1answer
28 views

Does the Prim algorith always create the same tree despite the starting node?

Does the Prim algorith always create the same tree despite the starting node? PD: sorry for my english.
2
votes
1answer
127 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
2
votes
1answer
104 views

spanning trees of an edge transitive graph

Let $G$ be an edge transitive graph. Let $t(G)$ be the number f spanning trees on $G$. Show that each edge lies in exactly $\tfrac{(n-1)t(G)}{m}$ spanning trees. Where $|V(G)|=n$ and $|E(G)=m$. ...
1
vote
4answers
646 views

How many labeled trees exist on n vertices with exactly 3 vertices of degree 1?

My combinatorics class is covering spanning trees right now and one of the questions being asked is "What is the number of labeled trees on n vertices with exactly $3$ vertices of degree $1$?" I've ...
0
votes
1answer
25 views

Question Concerning Family of Trees

I have the following problem where I am asked to construct a family of trees (one for each $n$) that have exactly 2 leaves. I am having difficulty with this problem mainly because I cannot find a ...
1
vote
0answers
34 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
1
vote
2answers
67 views

In a tree, is there always a sink where every longest path ends in?

Let $T$ be an undirected tree. Can we always find a leaf vertex $s$ such that every longest path of $T$ has its other endpoint in $s$? It's easy to see that every longest path passes through the ...
1
vote
2answers
84 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
0
votes
4answers
2k views

How many edges does an undirected tree with n nodes have?

The following options: a) $n$ b) $n + 1$ c) $n - 1$ d) $n(n - 1)$ e) $(n + 1)(n - 1)$ f) $\frac{n(n - 1)}2$ g) $\lceil \log_2n \rceil$
0
votes
0answers
49 views

Linear constraints on distance (hop) matrix of a tree

I have an optimization problem where I want the constraints to be linear. The variables are elements of an $N\times N$ matrix D. The elements of D, ie $D(i,j)$ are integers and represent the number of ...