Tagged Questions

32 views

Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
26 views

Proof that a local minimum in a spanning tree is also a minimum spanning tree.

Be $G$ a connected graph with weights associated to its edges. Be $T(G)$ the graph that has the spanning trees of $G$ as vertex, and two spanning trees are adjacent to each other if and only if each ...
26 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
16 views

Representing trees in Set builder notation?

Is there a way to represent graphs and minimum spanning trees using set builder notation? e.g. I have a weighted graph of n nodes, all connected to each other in a mesh network manner. I am to ...
31 views

Expected number of feed-forward/backward triangles in a random graph with internal nodes.

Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of: ...
52 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 ...
103 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 ...
56 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$.
78 views

How to prove that the smallest asymmetric tree has at least 7 vertices?

Find the smallest possible number of vertices an asymmetric tree can have (i.e. prove that no smaller tree can be asymmetric). I think that the answer is 7, but I don't know how to prove it.
40 views

Number of nodes with even offspring

I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end. Given a ...
99 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
76 views

Unique solution for a given pre- and post-order of a rooted tree

Decide the picture of a rooted tree with pre-order $a,b,c,d,e,f,g,h$ and post-order $d,e,f,g,h,c,b,a$. Show that there always is a unique solution for a given pre- and post-order of a rooted tree. My ...
589 views

Number of distinct path in a graph with $n$ vertices

Let $T = (V , E)$ be a tree with $|V | = n\geqslant 2$. How many distinct paths are there (as sub graphs) in $T$? I already have the answer to this question as $(n/2)$. The problem that I'm having is ...
88 views

Prove that there are two end points in a tree with a common neighbor

Let $T=(V,E)$ be a tree with at least $3$ vertices. Assume that every vertex has either degree $1$ or a degree of at least $3$ (so there are no vertices with degree $2$). Prove that there are two end ...
91 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 ...
93 views

spanning trees of graphs

Assume we have a simple connected graph G, how would start a prove of the following statement? For any edge of G, there is a spanning tree of G that contans it. I have decided that this is a true ...
245 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!
589 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 ...
58 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 ...
36 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!
141 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 ...
66 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*} ...
2k 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 ...
297 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$ ...
3k 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 ...
275 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 ...
92 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 ...
481 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 ...
653 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 ...