Graph theory gives students a clear way to study relationships by turning people into nodes and connections into edges. In a school social network project, a class can model friendships, follows, study partners, or club memberships using a labeled graph. This matters because the same ideas are used to understand online platforms, disease spread, recommendation systems, and teamwork patterns.
A small network can reveal structure that is hard to see from a list of names alone.
Students can collect a small, ethical sample of data, draw the graph, and calculate measurements such as degree, density, centrality, and cliques. These measurements help identify highly connected students, tightly connected groups, and how information might travel through the network. For an undirected friendship graph, an edge means both people share a connection, while a directed follow graph uses arrows to show direction.
The goal is not to judge people, but to practice mathematical modeling and learn how network structure affects real-world systems.
Key Facts
- A graph is written as G = (V, E), where V is the set of vertices or nodes and E is the set of edges.
- In an undirected graph, degree is the number of edges touching a node.
- In a directed graph, in-degree counts incoming arrows and out-degree counts outgoing arrows.
- Density for an undirected simple graph is D = 2E / (N(N - 1)), where N is the number of nodes and E is the number of edges.
- Density for a directed graph with no self-loops is D = E / (N(N - 1)).
- A clique is a group of nodes in which every pair of nodes is connected by an edge.
Vocabulary
- Node
- A node is a point in a graph that represents an object, such as a student profile in a social network.
- Edge
- An edge is a connection between two nodes, such as a friendship link or follow relationship.
- Degree
- Degree is the number of connections a node has in an undirected graph.
- Centrality
- Centrality is a measure of how important or influential a node is based on its position in the network.
- Clique
- A clique is a subgroup in which every member is directly connected to every other member.
Common Mistakes to Avoid
- Counting each undirected edge twice is wrong because a friendship edge between A and B is one connection, not two.
- Using the undirected density formula for a directed follow graph is wrong because directed graphs have more possible edges due to arrow direction.
- Calling any close-looking cluster a clique is wrong because every pair of nodes in the group must be directly connected.
- Treating high degree as the only kind of importance is wrong because a node can be important by connecting groups even if it has fewer total links.
Practice Questions
- 1 A friendship graph has 8 students and 10 undirected friendship edges. What is the density of the graph?
- 2 In a directed follow network, student A follows 5 people and is followed by 3 people. What are A's out-degree and in-degree?
- 3 A student with only 2 connections is the only bridge between two friend groups. Explain why this student might have high importance even without high degree.