Graph theory studies networks made of points and connections, which makes it useful for modeling roads, social networks, circuits, computer links, and schedules. A graph is built from vertices, often drawn as dots, and edges, drawn as lines connecting pairs of vertices. Even a small diagram can reveal important structure, such as which points are connected, which points are central, and which routes are possible.
These ideas help turn visual networks into precise mathematical objects that can be analyzed.
Understanding Math: Graph Theory Basics
Graphs become useful when each vertex has a clear meaning. In a road map, a vertex can represent an intersection, while an edge represents a road segment. In a school timetable, vertices can represent lessons, and an edge can show that two lessons share students or a teacher.
The choice of model matters. A road may have a length, travel time, cost, or traffic level. This value is called a weight.
Once weights are included, the shortest route is not always the route with the fewest edges. A longer route in distance may take less time if it avoids congestion.
Some connections have a direction. A one way street leads from one place to another but not necessarily back again. A social media follow can work the same way.
These are directed graphs. Each vertex then has an incoming degree and an outgoing degree. A page with many incoming links may be important because many other pages point to it.
A web search system can use this idea when judging which pages are widely referenced. Students should always check whether a situation needs undirected edges or directed edges. Treating every connection as two way can give a wrong answer.
Connectivity describes whether movement through a graph is possible. If every vertex can be reached from every other vertex, the graph is connected. If not, it has separate components.
This matters in communication networks. A broken cable can split one network into two groups that cannot exchange information. Certain vertices or edges are especially important.
Removing one of them may disconnect the graph. Such weak points help engineers decide where to add backup links. Trees are a special kind of connected graph with no cycles.
They are useful for showing family relationships, folder structures, and branching choices. Between any two vertices in a tree, there is exactly one route, so there is no ambiguity about the path.
Path problems often depend on the rule being used. A delivery worker who must cover every street is dealing with an edge problem. A tour that must visit every location is dealing with a vertex problem.
These sound similar, but they can be very different to solve. For an Euler route, odd degree vertices give a quick clue. An undirected connected graph can have an Euler circuit when every vertex has even degree.
It can have an Euler path with different start and end points when exactly two vertices have odd degree. Hamilton path problems do not have such a simple general test, so larger examples can be difficult.
When studying diagrams, label vertices clearly, list the connections carefully, and check every count twice. A missed edge can change the entire result.
Key Facts
- A graph is usually written as G = (V, E), where V is the set of vertices and E is the set of edges.
- The degree of a vertex is the number of edges that touch it.
- Handshake Lemma: sum of all vertex degrees = 2E for an undirected graph.
- A path is a sequence of vertices connected by edges, with no edge skipped between consecutive vertices.
- A cycle is a path that starts and ends at the same vertex and includes at least one edge.
- An Euler path uses every edge exactly once, while a Hamilton path visits every vertex exactly once.
Vocabulary
- Vertex
- A vertex is a point or node in a graph, often representing an object, location, or state.
- Edge
- An edge is a connection between two vertices in a graph.
- Degree
- The degree of a vertex is the number of edges incident to that vertex.
- Connected graph
- A connected graph is a graph in which there is a path between every pair of vertices.
- Cycle
- A cycle is a path that begins and ends at the same vertex without repeating edges in the simple case.
Common Mistakes to Avoid
- Counting vertices instead of edges for degree is wrong because degree depends only on how many edges touch a vertex.
- Assuming a graph is connected because it looks close together is wrong because connected means there must be an actual path between every pair of vertices.
- Confusing Euler paths with Hamilton paths is wrong because Euler paths focus on using every edge once, while Hamilton paths focus on visiting every vertex once.
- Counting each undirected edge twice in the edge total is wrong because an edge between A and B is one edge, even though it touches two vertices.
Practice Questions
- 1 A graph has vertices A, B, C, D and edges AB, AC, AD, BC, CD. Find the degree of each vertex and check the Handshake Lemma.
- 2 A connected graph has 8 vertices. The degrees of 7 vertices are 3, 2, 4, 1, 2, 5, and 3. What is the degree of the 8th vertex if the graph has 12 edges?
- 3 A graph has vertices A, B, C, D, E and edges AB, BC, CD, DE, EA, and AC. Explain whether A, B, C, D, E, A is a cycle, and explain whether it is an Euler path.