Question

Prove that if G = (V, E) is a tree and e ∈ E, then (V,...

Prove that if G = (V, E) is a tree and e ∈ E, then (V, E − {e}) is a forest of two trees.

Math   Statistics-And-Probability   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Answer:

Prove that if G = (V, E) is a tree and e ∈ E, then (V, E − {e}) is a forest of two trees:

Ler G=(V, E) is a tree.

Take e ∈ E. Now if e=xy.

i.e,

x and y are the endpoints of e.

If (V, E − {e}) is not a forest then it is a tree. but an x and y are adjacent vertices,

But then is a cycle that starts and ends at x.

But as, G=(V, E) is a tree, it can't contain a cycle.

So, our assumption that (V, E-{e}) is a forest that is a union of two trees.

(As we delete one edge and it connects only two points, only two new trees will be created).

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let G=(V,E) be a connected graph with |V|≥2 Prove that ∀e∈E the graph G∖e=(V,E∖{e}) is disconnected,...
Let G=(V,E) be a connected graph with |V|≥2 Prove that ∀e∈E the graph G∖e=(V,E∖{e}) is disconnected, then G is a tree.
Consider a minimum spanning tree for a weighted graph G= (V, E)and a new edge e,...
Consider a minimum spanning tree for a weighted graph G= (V, E)and a new edge e, connecting two existing nodes in V. Explain how to find a minimum spanning tree of the new graph in O(n)time, where n is the number of nodes in the graph. Prove correctness of the algorithm and justify the running time
A spanning tree of connected graph G = (V, E) is an acyclic connected subgraph (V,...
A spanning tree of connected graph G = (V, E) is an acyclic connected subgraph (V, E0 ) with the same vertices as G. Show that every connected graph G = (V, E) contains a spanning tree. (It is the connected subgraph (V, E0 ) with the smallest number of edges.)
Use induction to prove that every graph G = (V, E) satisfies χ(G) ≤ ∆(G).
Use induction to prove that every graph G = (V, E) satisfies χ(G) ≤ ∆(G).
Let T = (V, E) be a tree, and suppose that some node u ∈ V...
Let T = (V, E) be a tree, and suppose that some node u ∈ V has degree d. Prove that T has at least d leaves. Hint: Consider the induced subgraph with vertex set V \ {u}
Let e be the unique lightest edge in a graph G. Let T be a spanning...
Let e be the unique lightest edge in a graph G. Let T be a spanning tree of G such that e ∉ T . Prove using elementary properties of spanning trees (i.e. not the cut property) that T is not a minimum spanning tree of G.
Let T = (V, E) be a tree with |V | ≥ 2. Show that T...
Let T = (V, E) be a tree with |V | ≥ 2. Show that T has at least two vertices with degree 1.
Let G = (V,E) be a graph with n vertices and e edges. Show that the...
Let G = (V,E) be a graph with n vertices and e edges. Show that the following statements are equivalent: 1. G is a tree 2. G is connected and n = e + 1 3. G has no cycles and n = e + 1 4. If u and v are vertices in G, then there exists a unique path connecting u and v.
prove that if u and v are distinct vertices in a rooted tree which share a...
prove that if u and v are distinct vertices in a rooted tree which share a common descendant, then either u is the descendant of v or v is the descendant of u
Consider an undirected graph G = (V, E) with an injective cost function c: E →...
Consider an undirected graph G = (V, E) with an injective cost function c: E → N. Suppose T is a minimum spanning tree of G for cost function c. If we replace each edge cost c(e), e ∈ E, with cost c'(e) = c(e)2 for G, is T still a minimum spanning tree of G? Briefly justify your answer.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT