Discrete Mathematics: Elementary and Beyond

7.2 Paths, Cycles, and Connectivity 131 The first and last nodes in the row are called theendpointsof the path. If we also conne ...

132 7. Graphs FIGURE 7.6. A path in a graph connecting two nodes the nodes on the first part of our walk are distinct because th ...

7.2 Paths, Cycles, and Connectivity 133 aa b b c c FIGURE 7.7. Selecting a path fromatoc, given a path fromatoband a path frombt ...

134 7. Graphs 7.2.7LetGbe a graph, and letH 1 =(V 1 ,E 1 ) andH 2 =(V 2 ,E 2 ) be two subgraphs ofGthat are connected. Assume th ...

7.3 Eulerian Walks and Hamiltonian Cycles 135 7.3 Eulerian Walks and Hamiltonian Cycles Perhaps the oldest result in graph theor ...

136 7. Graphs Euler published a paper in 1736 in which he proved that such a walk was impossible. The argument is quite simple. ...

7.3 Eulerian Walks and Hamiltonian Cycles 137 a walk that crosses every bridge exactly once corresponds to an Eulerian walk. FIG ...

138 7. Graphs pandqare the endpoints ofeandWdoes not pass through them, then we take a path fromptov(such a path exists since th ...

7.3 Eulerian Walks and Hamiltonian Cycles 139 FIGURE 7.12. Which of these graphs has an Eulerian walk? 7.3.2When does a connecte ...

140 7. Graphs Review Exercises 7.3.4Draw all graphs on 5 nodes in which every node has degree at most 2. 7.3.5Does there exists ...

8 Trees 8.1 How to Define Trees We have met trees when we were studying enumeration problems; now we take a look at them as grap ...

142 8. Trees will still not contain a cycle (while adding a new edge may create a cycle). The following theorem shows that trees ...

8.2 How to Grow Trees 143 v. The other neighbors ofvare called thesonsofv. The rootrdoes not have a father, but all its neighbor ...

144 8. Trees nodes and edges we have traversed between the two visits form a cycle. This contradicts our assumption thatGis a tr ...

8.2 How to Grow Trees 145 By the induction hypothesis, every tree with fewer nodes thanGarises by the construction; in particula ...

146 8. Trees 8.2.3If we delete a nodevfrom a tree (together with all edges that end there), we get a graph whose connected compo ...

8.3 How to Count Trees? 147 between the nodes of the first tree and the nodes of the second tree such that two nodes in the firs ...

148 8. Trees 8.4 How to Store Trees....................... Suppose that you want to store a labeled tree, say the tree in Figure ...

8.4 How to Store Trees 149 down the label of a node takes log 2 nbits, so the whole table occupies only 2 nlog 2 nbits, which is ...

150 8. Trees (d) Now we describe a procedure, called thePr ̈ ufer code, that will assign to anyn-point labeled tree a sequence o ...