Graph Theory Basics & the Handshaking Lemma (Discrete Mathematics)
Free printable Discrete Mathematics worksheet introducing graph terminology (vertices, edges, degree) and the handshaking lemma: degree sums, counting edges from a degree sequence, and impossible degree sequences, all generated from explicitly constructed graphs.
✓ Answer key checked by math, never wrong
Discrete Mathematics · Math worksheet
Name
Date
Math
Graph Theory Basics & the Handshaking Lemma
A graph is a set of vertices joined by edges; the degree of a vertex is the number of edges meeting it. Read each degree from the listed edge set. The handshaking lemma says the sum of all the degrees equals twice the number of edges, because every edge has exactly two endpoints; in particular the degree sum is always even.
- 1.Graph G has vertex set {A, B, C, D, E} and edge set {B-D, C-E, C-D, A-D, A-E, D-E, B-E, A-C}. What is the degree of vertex A?
- 2.Graph G has vertex set {A, B, C, D, E, F} and edge set {B-D, B-F, A-B, B-E, C-E, A-E, D-E, B-C}. What is the degree of vertex B?
- 3.Graph G has vertex set {A, B, C, D, E} and edge set {C-D, B-D, A-C, A-B, D-E, C-E, A-E}. What is the degree of vertex E?
- 4.Graph G has vertex set {A, B, C, D, E} and edge set {B-C, B-E, A-B, C-E, A-C, C-D, B-D}. Find the sum of the degrees of all the vertices, and state how it relates to the number of edges.
- 5.Graph G has vertex set {A, B, C, D, E, F} and edge set {E-F, C-F, B-E, B-C, D-F, C-E, D-E, A-F, A-C}. Find the sum of the degrees of all the vertices, and state how it relates to the number of edges.
- 6.The 6 vertices of a graph have degrees 4, 4, 3, 3, 1, 1. Using the handshaking lemma, how many edges does the graph have?
- 7.The 6 vertices of a graph have degrees 2, 1, 2, 2, 4, 3. Using the handshaking lemma, how many edges does the graph have?
- 8.Can a graph have exactly 5 vertices with degrees 4, 3, 3, 3, 2? Answer Yes or No, using the handshaking lemma.
- a) Yes
- b) No
- 9.Can a graph have exactly 5 vertices with degrees 3, 3, 3, 3, 2? Answer Yes or No.
- a) Yes
- b) No
- 10.Graph G has vertex set {A, B, C, D, E, F} and edge set {E-F, A-B, C-E, B-F, C-D, B-D}. How many vertices of G have odd degree?
Made with ChalkBee · chalkbee.com