CSCC73H3 Quiz: cut-property
2 Mar 2017
School
Department
Course
Professor
Document Summary
In this handout we use graph to mean undirected, connected graph , and tree to mean free tree (i. e. , an undirected, connected, acyclic graph). You already know that a tree with n nodes has n 1 edges. Using this, you can easily prove the following fact: adding an edge to a tree creates a unique cycle; removing any edge from that cycle yields a tree again. Fact 1 let t = (v, e) be a tree and e be an edge not in e. then the graph t + = (v, e {e}) has a unique cycle. Furthermore, if e is any edge on that cycle, the graph t = (cid:0)v, (e {e}) e (cid:1) is a tree. An edge e of g crosses the cut (s, v s) if one of the endpoints of e is in s and the other is in v s. Then f {e} is also contained in a mst of g.
