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.
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.