Graph Theory Fundamentals
This worksheet covers fundamental concepts in graph theory including definitions, types of graphs, and basic properties.
Includes
Standards
Topics
Graph Theory Fundamentals
Name:
Date:
Score:
Read each question carefully and answer to the best of your ability. Show all your work where applicable.
1. Which of the following best defines a graph in graph theory?
A collection of lines and curves.
A set of vertices and a set of edges connecting pairs of vertices.
A diagram showing relationships between data points.
A system of equations.
2. In a simple graph, what is true about its edges?
They can connect a vertex to itself (loops).
There can be multiple edges between the same pair of vertices.
They are undirected and connect distinct pairs of vertices without loops or multiple edges.
They always have a direction.
1. A graph with no edges is called a graph.
2. The of a vertex is the number of edges incident to it.
3. A path in a graph that visits every vertex exactly once is called a path.
1. Draw a simple graph with 5 vertices and 4 edges. Label your vertices.
2. Explain the difference between a directed graph and an undirected graph.
1. A connected graph is a graph in which there is a path between every pair of distinct vertices.
True
False
2. A tree is an undirected graph in which any two vertices are connected by exactly one path.
True
False
Match each term on the left with its definition on the right.
1. Vertex
a. A connection between two vertices.
2. Edge
b. A point or node in a graph.
3. Degree
c. The number of edges incident to a vertex.
Use the words below to complete the sentences.
1. A graph where every pair of distinct vertices is connected by a unique edge is called a graph.
2. A graph is one whose vertices can be divided into two disjoint and independent sets.
3. A is a closed path in a graph where no vertex is repeated except for the start and end vertex.