18.2.5. Formal Definition of a Graph

Try these first

1. 1.

   Define a vertex in the context of a graph.

   Hint

   Think of it as a location in the graph.

2. 2.

   What is an edge?

   Hint

   Consider how two points can be joined in a diagram.

3. 3.

   What is a graph?

   • A set of edges only
   • A set of vertices only
   • A set of vertices and edges

   Hint

   Remember what makes up a graph.

4. 4.

   True or False: In a directed graph, all edges are bidirectional.

   • True
   • False

   Hint

   Think about the directionality of relationships in graphs.

5. 5.

   Prove that any planar graph can be colored using no more than four colors.

   Hint

   Review the Four Color Theorem.

6. 6.

   Describe how you would find the shortest path between two vertices in a directed graph.

   Hint

   Think about algorithms you've learned that deal with pathfinding.