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.
The 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
Tiny 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 this kind of problem
- 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.