# Tagged Questions

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.

10k views

33 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 ...
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 ...
17 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 ...
220 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
30 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 ...
40 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 ...
85 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 &...
181 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 ...
18 views

30 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 ...
143 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 ...
88 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 =...
38 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 ...
24 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 ...
58 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?
### 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 ...