0 like 0 dislike
4 views
What are spanning trees in graph theory?
in General Maths by Diamond (39.8k points) | 4 views

1 Answer

0 like 0 dislike
Best answer
A spanning subgraph that is also a tree is called a spanning tree.

Theorem:
A graph G is connected iff G has a spanning tree.

Theorem:
If T is a spanning tree of G and e is an edge not in T, then T + e contains exactly one cycle C. Moreover, if e' is any edge on C, then T + e - e' is also a spanning tree of G.

Theorem:
If T is a spanning tree of G and e is an edge in T, then T - e has 2 components. Moreover, if e' is in the cut induced by one of the components, then T - e + e' is also a spanning tree of G.
by Diamond (39.8k points)

Related questions

0 like 0 dislike
1 answer
asked Apr 25 in General Maths by Tedsf Diamond (39.8k points) | 7 views
0 like 0 dislike
0 answers
asked Aug 30, 2019 in SysAdmin Skills by Tedsf Diamond (39.8k points) | 10 views
0 like 0 dislike
1 answer
asked Apr 25 in General Maths by Tedsf Diamond (39.8k points) | 6 views
0 like 0 dislike
1 answer
asked Mar 6, 2019 in Grade 3 Maths by Tedsf Diamond (39.8k points) | 17 views
Welcome to MathsGee Skills Question and Answer Bank, a platform, where you can ask study questions and receive answers from other members of the community. Help is always 100% FREE!
MathsGee Q&A is the knowledge-sharing community where millions of students and experts put their heads together to crack their toughest homework questions.

Enter your email address:

[consumerlti id="python_coding"]