Introduction to Graph Theory
This worksheet introduces fundamental concepts in graph theory, including definitions, types of graphs, and basic properties, suitable for Grade 12 mathematics students.
Includes
Standards
Topics
Introduction to Graph Theory
Name:
Date:
Score:
Read each question carefully and answer to the best of your ability. Show all your work for short answer questions.
1. Which of the following best describes a 'vertex' in graph theory?
A connection between two points
A point or node in the graph
The path taken between vertices
The number of edges connected to a vertex
2. A graph where all vertices have the same degree is called a:
Complete graph
Regular graph
Connected graph
Bipartite graph
3. A graph with no cycles is called a .
4. The sum of the degrees of all vertices in a graph is always equal to twice the number of .
5. In a directed graph, an edge has a .
6. A walk in a graph that visits every vertex exactly once is called a Hamiltonian path.
True
False
7. A complete graph with 'n' vertices has n(n-1)/2 edges.
True
False
8. Define what an 'Eulerian circuit' is in the context of graph theory.
9. Explain the difference between a 'path' and a 'trail' in graph theory.
10. Consider a graph G with vertices V = {A, B, C, D} and edges E = {(A,B), (A,C), (B,C), (C,D)}. Draw this graph and list the degree of each vertex.
11. For the graph drawn in question 10, determine if it is connected. Justify your answer.