Graphs / Basic Graphs
Least You Need to Know: Basic Graphs
Graphs model objects as vertices and connections as edges. Most beginner mistakes come from miscounting degree or confusing paths with edges.
Least you need to know
- The degree of a vertex is the number of incident edges.
- A path is a sequence of vertices connected by edges.
- The sum of all vertex degrees equals twice the number of edges in an undirected graph.
- Adjacent vertices are joined by an edge.
Key notation
- V — vertex set
- E — edge set
- deg(v) — degree of vertex v
Worked example
- Graph with edges {ab, ac, bc, cd}.
- deg(c)=3 because c touches ac, bc, and cd.
- The graph has 4 edges, so the total degree sum is 8.
Common mistakes
- Students often count vertices instead of incident edges.
- Students often forget that one edge contributes to two degrees in an undirected graph.
- Students often call any walk a path without checking repetition rules.
How to recognize it
- If you need edges from degrees, use the handshake idea.
- When counting a degree, physically list touching edges.
- If the graph is undirected, each edge raises two degrees total.
Next recommended lesson
Continue through this topic with Least You Need to Know: Bipartite Graphs.
Least You Need to Know: Bipartite GraphsRelated lessons
Keep going with nearby lessons in the same topic.