maths.free › Discrete Math & Logic › Graphs: degrees, paths and connectivity
Graphs: degrees, paths and connectivity
Vertices and edges, the handshake lemma, walks, paths and cycles, connected components, and the adjacency matrix.
A graph \( G = (V, E) \) is a set of vertices and a set of edges, each edge joining two vertices. In a simple graph there are no loops and no repeated edges, so a simple graph on \( n \) vertices has at most \( \binom{n}{2} \) edges, a number reached only by the complete graph \( K_n \); the example finds that \( K_7 \) has 21 edges. The degree \( \deg v \) is the number of edges at \( v \). Graphs model anything with pairwise connections: roads, friendships, molecules, web links, conflicts in a timetable.
Every edge has two ends, so adding up all the degrees counts each edge exactly twice. That is the handshake lemma: \[ \sum_{v \in V} \deg v = 2|E|. \] Two consequences follow immediately. The number of vertices of odd degree is even, since the total is even. And a degree sequence can only belong to a graph if its sum is even: no graph has degrees 3, 3, 3, 2, since they sum to 11. An even sum is necessary but not sufficient; the sequence 3, 3, 1, 1 has sum 8 but is not the degree sequence of a simple graph, because two vertices of degree 3 among four vertices would each have to be joined to both vertices of degree 1.
A walk is a sequence of vertices, each joined to the next by an edge. A path is a walk with no repeated vertex, and a cycle is a closed walk with no repeated vertex apart from the start. A graph is connected if every two vertices are joined by a path; in general it splits into connected components. A connected graph on \( n \) vertices needs at least \( n - 1 \) edges, and the distance between two vertices is the length of a shortest path, which breadth-first search finds.
The adjacency matrix \( A \) has \( A_{ij} = 1 \) when \( i \) and \( j \) are adjacent and 0 otherwise. Its powers count walks: \( (A^k)_{ij} \) is the number of walks of length \( k \) from \( i \) to \( j \), because a walk of length \( k \) is a walk of length \( k - 1 \) followed by one edge, which is exactly how matrix multiplication combines entries. In particular the diagonal of \( A^2 \) holds the degrees, and the trace of \( A^3 \) is six times the number of triangles.
Picture it: dots and lines. Degree is how many lines leave a dot; a component is a piece of the drawing you could pick up without breaking a line; a path is a route you could trace with a finger without visiting a dot twice. The drawing is not the graph: move the dots anywhere and it is the same graph as long as the same pairs stay joined.
Think it: many graph facts are double counting in disguise. The handshake lemma counts (vertex, edge) incidences two ways, and the walk formula counts walks by their last step. When a graph question asks "how many", ask what you could count twice.
Worked example · 7 choose 2
Step by step
- \binom{7}{2} = \frac{7!}{2!\,(7-2)!}
Unordered selections: n! / (k! (n−k)!).
- = \frac{5040}{2 \times 120} = 21
Reveal the answer
Now you Pick a problem, or type or draw your own. Every step, a picture, the answer hidden until you ask.
Symbols used here
Tap any symbol for the full definition, a picture, and what every letter in it means.
How to: Graphs: degrees, paths and connectivity
- List the vertices and edges, or read them from a drawing.
- Compute degrees and check the handshake lemma: the sum is twice the number of edges.
- To test connectivity, grow the set of vertices reachable from one vertex until it stops changing.
- To count walks of length k between two vertices, compute the matching entry of the k-th power of the adjacency matrix.
Questions people ask
Can a party have an odd number of people who each shook an odd number of hands?
No. By the handshake lemma the number of odd-degree vertices is always even.
What is the difference between a walk, a trail and a path?
A walk may repeat vertices and edges, a trail may repeat vertices but not edges, and a path repeats neither.
What makes mathematics "discrete"?
It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.
How does a proof by induction work?
Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.
What order should I take these lessons in?
Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.
Is discrete mathematics the same as the maths of computer science?
Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.
Do I need calculus for this course?
No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.
More in Discrete Math & Logic
Truth tablesSums and inductionProof by inductionAlgorithms and growth of functionsPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsThe pigeonhole principleSolving linear recurrence relationsTrees and spanning treesEuler and Hamilton paths