xvi Contents 5.7 Probability Distributions and Variance 343 Distributions of Random Variables 343 Variance 346 Important Concepts,Formulas,and Theorems 354 Problems 355 CHAPTER 6 Graphs 359 6.1 Graphs 359 The Degree of a Vertex 363 Connectivity 365 Cycles 367 Trees 368 Other Properties of Trees 368 Important Concepts,Formulas,and Theorems 371 Problems 373 6.2 Spanning Trees and Rooted Trees 375 Spanning Trees 375 Breadth-First Search 377 Rooted Trees 382 Important Concepts,Formulas,and Theorems 386 Problems 387 6.3 Eulerian and Hamiltonian Graphs 389 Eulerian Tours and Trails 389 Finding Eulerian Tours 394 Hamiltonian Paths and Cycles 395 NP-Complete Problems 401 Proving That Problems Are NP-Complete 403 Important Concepts,Formulas,and Theorems 406 Problems 407 6.4 Matching Theory 410 The Idea of a Matching 410 Making Matchings Bigger 414xvi Contents 5.7 Probability Distributions and Variance 343 Distributions of Random Variables 343 Variance 346 Important Concepts, Formulas, and Theorems 354 Problems 355 CHAPTER 6 Graphs 359 6.1 Graphs 359 The Degree of a Vertex 363 Connectivity 365 Cycles 367 Trees 368 Other Properties of Trees 368 Important Concepts, Formulas, and Theorems 371 Problems 373 6.2 Spanning Trees and Rooted Trees 375 Spanning Trees 375 Breadth-First Search 377 Rooted Trees 382 Important Concepts, Formulas, and Theorems 386 Problems 387 6.3 Eulerian and Hamiltonian Graphs 389 Eulerian Tours and Trails 389 Finding Eulerian Tours 394 Hamiltonian Paths and Cycles 395 NP-Complete Problems 401 Proving That Problems Are NP-Complete 403 Important Concepts, Formulas, and Theorems 406 Problems 407 6.4 Matching Theory 410 The Idea of a Matching 410 Making Matchings Bigger 414