Graph Theory: Industrial Drilling
Home
>
Graph Theory: Industrial Drilling
> Foundations > Trees
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home
The Drilling Problem
Objectives
Foundations
What is a Graph?
Edges and Vertices
A First Theorem
Types of Graphs
Subgraphs and Supergraphs
Walks, Paths, Cycles
Trees
Solving the Drilling Problem
Independent Sets, Cliques, etc.
Vertex Coloring
Modeling it as a Graph Theory Problem
First Lower Bound
The Inside View
A Good Coloring
The Best Coloring
What's Next?
concepts
discover
apply
collaborate
practice
Trees
Trees
Problem 19:
Prove that for every tree, the number of edges is one less than the number of vertices.
Figure 21:
Answer
Copyright 1999 Rensselaer Polytechnic Institute. All Rights Reserved.