Contents xiii Properties of Trees 414 Leaves 416 Spanning Trees 418 Recap 419 Exercises 420 50 Eulerian Graphs 421 Necessary Conditions 422 Main Theorems 423 Unfinished Business 425 Recap 426 Exercises 426 51 Coloring 427 Core Concepts 427 Bipartite Graphs 429 The Ease of Two-Coloring and the Difficulty of Three-Coloring 433 Recap 434 Exercises 434 52 Planar Graphs 435 Dangerous Curves 435 Embedding 436 Euler's Formula 437 Nonplanar Graphs 440 Coloring Planar Graphs 442 Recap 444 Exercises 444 Chapter 9 Self Test 446 10 Partially Ordered Sets 449 53 Fundamentals of Partially Ordered Sets 449 What Is a Poset? 449 Notation and Language 452 Recap 454 Exercises .454 54 Max and Min 455 Recap 457 Exercises 457 55 Linear Orders 458 Recap 460 Exercises 46110 Properties of Trees 414 Leaves 416 Spanning Trees 418 Recap 419 Exercises 420 50 Eulerian Graphs Necessary Conditions 421 422 Main Theorems 423 Unfinished Business. 425 Recap 426 Exercises 426 51 Coloring 427 Core Concepts 427 Bipartite Graphs 429 The Ease of Two-Coloring and the Difficulty of Three-Coloring 433 Recap 434 Exercises 434 52 Planar Graphs 435 Dangerous Curves 435 Embedding 436 Euler's Formula 437 Nonplanar Graphs 440 Coloring Planar Graphs 442 Recap 444 Exercises 444 Chapter 9 Self Test 446 Partially Ordered Sets 449 53 Fundamentals of Partially Ordered Sets 449 What Is a Poset? 449 Notation and Language 452 Recap 454 Exercises 454 54 Max and Min 455 Recap 457 Exercises 457 55 Linear Orders 458 Recap 460 Exercises 461 Contents xiii