Introduction to Graph Theory: Nodes and Edges
Modeling connections with points and lines
Introduction to Graph Theory: Nodes and Edges
Modeling connections with points and lines
Math - Grade 6-8
- 1
A graph has 5 nodes labeled A, B, C, D, and E. It has edges AB, AC, BD, DE, and CE. How many nodes and how many edges are in the graph?
Count the labels for the nodes and count each listed connection for the edges.
The graph has 5 nodes and 5 edges. The nodes are A, B, C, D, and E, and the edges are AB, AC, BD, DE, and CE. - 2
In a graph, what is the difference between a node and an edge? Give a real-world example of each.
A node is a point or object in a graph, and an edge is a connection between two nodes. For example, in a map of flights, airports can be nodes and flight routes can be edges. - 3
A friendship graph shows four students: Maya, Luis, Priya, and Jordan. Maya is friends with Luis and Priya. Luis is friends with Jordan. Priya is friends with Jordan. List all the edges in the graph.
Write one edge for each friendship mentioned.
The edges are Maya-Luis, Maya-Priya, Luis-Jordan, and Priya-Jordan. Each edge represents one friendship between two students. - 4
Look at a graph with nodes P, Q, R, and S. The edges are PQ, QR, RS, and SP. Draw the graph and describe its shape.
The graph forms a cycle with four nodes. If drawn with the nodes in order P, Q, R, and S, the edges make a square or rectangle shape. - 5
A graph has nodes A, B, C, and D. Every pair of nodes is connected by exactly one edge. How many edges does the graph have?
List all possible pairs of the four nodes without repeating a pair.
The graph has 6 edges. The edges are AB, AC, AD, BC, BD, and CD. - 6
The degree of a node is the number of edges that touch it. In a graph, node X is connected to A, B, C, and D. What is the degree of node X?
The degree of node X is 4 because four edges touch node X. - 7
A road map can be modeled as a graph. Suppose towns are nodes and roads are edges. If there is a road from Town A to Town B and a road from Town B to Town C, but no road from Town A to Town C, what edges should be included?
Only draw an edge when there is a direct road between two towns.
The graph should include edges A-B and B-C. It should not include edge A-C because there is no direct road between Town A and Town C. - 8
A graph has 7 nodes and 0 edges. What does this tell you about the connections in the graph?
It tells us that there are 7 separate nodes and no connections between them. No node is connected to any other node by an edge. - 9
In the graph with edges AB, AC, BC, CD, and DE, find the degree of node C.
Count only the edges that include the letter C.
The degree of node C is 3. Node C is connected by edges AC, BC, and CD. - 10
Create a simple graph to model a group project with 5 students. Each edge should mean that two students worked together. Your graph must have at least 4 edges. Then write the list of edges you used.
Label the students A, B, C, D, and E, then choose at least four pairs to connect.
Answers will vary. A correct answer should include 5 nodes for the 5 students and at least 4 edges showing pairs of students who worked together, such as AB, AC, BD, CE, and DE.