MTH 208 Lecture 15: 11.12-14
7 May 2020
School
Department
Course
Professor
Document Summary
Fact everypartof vertices in a tree are joinedby a uniquepath. Ref let a b bevertices in a tree sincetree is connected there is at. Suppose there are 2 paths between a and b. Since t is a tree cannot antam cycles hence there camecontradiction least one ai b path in t be two a b paths pi p2 in t. In a graph g our edge e b called a bridgefor a if removing e increases the number of connected components cut edge i. e disconnects a component de c ez. Det h is a spanning subgraph of g if it is a subgraph containing all vertices of g. A spanning thee is a spanning subgraph that is a tree. Trim adding an edgeof g to a spanning tree of g creates a cycle. Defy a leaf 13 a vertex that is incident to only one edge. The edge of the leaf b called pendant.
