A connected graph has exactly two vertices of odd degree. It therefore has:

An Euler path but no Euler circuit

An Euler circuit but no Euler path

An Euler path but no Euler circuit

Both an Euler circuit and a Hamiltonian cycle

Neither an Euler path nor an Euler circuit

In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. This is:

True for every graph, not just bipartite ones

Which of the following are true for every tree T on n ≥ 2 vertices? (More than one option may be correct.)

T has at least two vertices of degree 1

Graph Theory — Connectivity, Matching and Colouring

Graph questions look like they need a drawing and usually need an identity. The one to reach for first is the handshaking lemma: the sum of all degrees equals twice the number of edges, so the degree sum is always even and the number of odd-degree vertices is always even. That single parity fact settles a whole family of "does such a graph exist" questions without any construction — a graph with five vertices each of degree three would have degree sum 15, which is odd, so it cannot exist. Three more identities do most of the remaining work. A tree on n vertices has exactly n − 1 edges and a unique path between any two vertices, so a connected graph with more than n − 1 edges must contain a cycle and one with fewer cannot be connected at all. The complete graph Kₙ has n(n − 1)/2 edges. And Euler's formula v − e + f = 2 holds for any connected planar graph drawn without crossings, which is how planarity questions become arithmetic. On the two named topics: a graph is bipartite exactly when it has no odd cycle, which is far easier to test than trying to two-colour it by hand; and its chromatic number is bounded below by the size of its largest clique and above by Δ + 1, with χ(Kₙ) = n, χ(even cycle) = 2 and χ(odd cycle) = 3. Matching has one result worth knowing by name — König's theorem, that in a bipartite graph the largest matching and the smallest vertex cover have the same size — because it converts a question you cannot see the answer to into one you can. Finally, the Euler-trail conditions are pure parity again: a connected graph has a closed Euler circuit exactly when every degree is even, and an open Euler path exactly when precisely two degrees are odd.

The Counting Identities

Five identities, and the question each one answers
Identity	What it settles
Σ deg(v) = 2\|E\|	Existence by parity. Five vertices of degree 3 give a degree sum of 15 — odd, so no such graph. The number of odd-degree vertices is always even.
A tree on n vertices has n − 1 edges	Cycles and connectivity. More than n − 1 edges in a connected graph forces a cycle; fewer than n − 1 makes connection impossible.
\|E(Kₙ)\| = n(n − 1)/2	Upper bounds. K₅ has 10 edges; any simple graph on n vertices has at most that many.
A k-regular graph on n vertices has nk/2 edges	Both existence and counting. A 3-regular graph on 6 vertices has 9 edges; on 5 vertices it cannot exist, since nk is odd.
v − e + f = 2 (connected planar)	Faces and planarity. K₄ drawn flat has v = 4, e = 6, so f = 4. K₅ and K₃,₃ are the two minimal non-planar graphs.

🧠 Cayley: nⁿ⁻² labelled trees

The number of distinct labelled trees on n vertices is n⁽ⁿ⁻²⁾ — 16 on four vertices, 125 on five. The exponent is easy to get wrong, so anchor it on the smallest case you can check by hand: on three vertices the formula gives 3¹ = 3, and there really are three labelled trees on {a, b, c}, one for each choice of middle vertex. Note what the count is of: labelled trees, where the vertices are distinguishable. The number of unlabelled tree shapes is a different and much smaller sequence, and a question that says "labelled" is saying which one it wants.

Colouring, and the Odd-Cycle Test

A graph is bipartite exactly when it contains no odd cycle. That is the test to run — searching for an odd cycle is far quicker than attempting a two-colouring and backtracking. Every tree is bipartite, since a tree has no cycles at all.
χ(Kₙ) = n, because every pair of vertices is adjacent and no two can share a colour. More generally χ(G) is at least the size of the largest clique, which is the lower bound to reach for first.
χ(cycle) is 2 if the cycle is even and 3 if it is odd. C₆ needs two colours, C₅ needs three, and the jump happens for the same reason bipartiteness fails: going round an odd cycle forces two adjacent vertices to agree.
Every planar graph is 4-colourable, and every graph is (Δ + 1)-colourable where Δ is the largest degree. Both are upper bounds, and a question asking for the exact chromatic number usually wants the clique bound from below and one of these from above, meeting at a single value.

🎯 König: matching and covering are the same number in a bipartite graph

A matching is a set of edges no two of which share a vertex; a vertex cover is a set of vertices touching every edge. In any graph the largest matching is at most the smallest cover, since each matched edge needs its own cover vertex. König's theorem says that in a bipartite graph the two are equal — which is useful in both directions: exhibit a matching of size k and a cover of size k, and you have proved both are optimal without searching further. For the bipartite graph with edges {(1,4), (1,5), (2,5), (3,6)} the largest matching is {(1,4), (2,5), (3,6)}, of size 3, so the smallest vertex cover also has size 3. The equality is false for general graphs — an odd cycle breaks it — which is why the word "bipartite" in a matching question is doing real work.

Euler Trails — Parity Again

For a connected graph: a closed Euler circuit exists exactly when every vertex has even degree, and an open Euler path exactly when exactly two vertices have odd degree — those two being the endpoints. There is no third case, because the number of odd-degree vertices is always even. So the answer to any Euler question is a degree count, and the bridges of Königsberg fail because all four of its vertices are odd.

⚠️ Euler is about edges, Hamilton is about vertices

An Euler trail uses every edge once; a Hamiltonian cycle visits every vertex once. The two are not variants of one problem: Euler has the clean parity criterion above and is decidable in linear time, while no such criterion is known for Hamiltonicity and deciding it is NP-complete. A question that offers a degree-parity argument as the reason a Hamiltonian cycle exists is offering a wrong reason for a possibly right answer, and that is the standard distractor here.

Key takeaways

Σ deg(v) = 2|E|, so the degree sum is even and the number of odd-degree vertices is even. Five vertices of degree 3 cannot exist.
A tree on n vertices has n − 1 edges. More than that in a connected graph forces a cycle; fewer makes connection impossible.
Cayley: nⁿ⁻² labelled trees on n vertices — 16 on four, 125 on five. Anchor the exponent on n = 3, where the answer is 3.
Bipartite exactly when there is no odd cycle — test for the cycle rather than attempting a two-colouring.
χ(Kₙ) = n, χ(even cycle) = 2, χ(odd cycle) = 3. The clique size bounds χ from below and Δ + 1 from above.
König: in a bipartite graph the largest matching equals the smallest vertex cover. The equality fails for general graphs.
An Euler circuit needs all degrees even; an Euler path needs exactly two odd. Euler is about edges, Hamilton about vertices, and only Euler has a parity criterion.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

How many simple graphs are there in which every one of 5 vertices has degree exactly 3?
1. Exactly one
2. Exactly two
3. None — no such graph exists
4. Infinitely many
Show answer
Answer: C — None — no such graph exists
By the handshaking lemma the degree sum is twice the edge count, so it must be even. Here the sum is 5 × 3 = 15, which is odd — so no such graph exists, and the answer needs no attempt at construction. The general form is worth carrying: a k-regular graph on n vertices exists only when nk is even, which is why 3-regular graphs exist on 4, 6, 8 … vertices and never on an odd number of them. Option D can be dismissed on principle too — there are only finitely many graphs on a fixed vertex set, since a graph is a subset of the at most n(n − 1)/2 possible edges.
The chromatic number of a cycle on 5 vertices is:
1. 2
2. 3
3. 4
4. 5
Show answer
Answer: B — 3
Go round the cycle alternating two colours: after five steps you return to the start having used the same colour on both ends of an edge, so two colours are impossible — an odd cycle is not bipartite. Three suffice: colour four vertices alternately and give the fifth the third colour. So χ(C₅) = 3. Option A is the answer for an even cycle, and offering it is the whole point of choosing 5 rather than 6. Option D is χ(K₅), which is a different graph on the same vertex count — C₅ has 5 edges and K₅ has 10, and confusing the two is worth guarding against whenever a question names only the vertex count.
A connected simple graph has 6 vertices and 6 edges. Which of the following must be true?
1. It is a tree
2. It contains at least one cycle
3. It is bipartite
4. It has a vertex of degree 5
Show answer
Answer: B — It contains at least one cycle
A tree on 6 vertices has exactly 5 edges, and a connected graph with more edges than that must contain a cycle — 6 > 5, so it contains at least one cycle. That also rules out option A directly. Option C is not forced: adding one edge to a tree can create an odd cycle, and a graph with an odd cycle is not bipartite, so bipartiteness is possible but not necessary. Option D is not forced either — the degree sum is 12, which can be spread as 2, 2, 2, 2, 2, 2 in a 6-cycle with no vertex above degree 2. The useful habit is to compare the edge count with n − 1 first: below it the graph cannot be connected, at it the graph is a tree, above it there is a cycle.
A connected graph has exactly two vertices of odd degree. It therefore has:
1. An Euler circuit but no Euler path
2. An Euler path but no Euler circuit
3. Both an Euler circuit and a Hamiltonian cycle
4. Neither an Euler path nor an Euler circuit
Show answer
Answer: B — An Euler path but no Euler circuit
Exactly two odd-degree vertices is precisely the condition for an open Euler path, and those two vertices are forced to be its endpoints. A closed Euler circuit needs every degree even, so it is ruled out. Option C adds a Hamiltonian claim that nothing here supports: Euler conditions say nothing about Hamiltonicity, which has no known degree criterion and is NP-complete to decide — offering the two together is the standard distractor in this topic. Note also that "exactly one odd vertex" is never a case to consider, since the number of odd-degree vertices is always even.
In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. This is:
1. Euler’s theorem
2. König’s theorem
3. Cayley’s formula
4. True for every graph, not just bipartite ones
Show answer
Answer: B — König’s theorem
This is König's theorem, and the word "bipartite" in it is load-bearing. In any graph the maximum matching is at most the minimum vertex cover, because each matched edge needs a distinct cover vertex; König says the two are equal in a bipartite graph. Option D is the trap and is false: take a triangle, whose maximum matching is 1 while its minimum vertex cover is 2. That single counterexample is worth remembering because it is also the smallest odd cycle, and odd cycles are exactly what bipartiteness excludes. The practical use is a proof shortcut — display a matching and a cover of the same size and both are optimal, with no further search.
Which of the following are true for every tree T on n ≥ 2 vertices? (More than one option may be correct.)
1. T has exactly n − 1 edges
2. T is bipartite
3. T has at least two vertices of degree 1
4. T has a Hamiltonian cycle
Show answer
Answer: A — T has exactly n − 1 edges; B — T is bipartite; C — T has at least two vertices of degree 1
Three hold. A is the defining count. B holds because a tree has no cycles at all, so it certainly has no odd cycle — every tree is 2-colourable. C is the leaf lemma: the degree sum is 2(n − 1), so the average degree is under 2, and a connected graph in which fewer than two vertices had degree 1 would exceed that. Only D fails, and it fails for the most direct reason available: a Hamiltonian cycle is a cycle, and a tree has none. Note how D is the one option that contradicts the definition rather than merely going beyond it — the fastest route through an MSQ like this is to check each option against the definition first and only then look for a counterexample.
The number of distinct labelled trees on 5 vertices is _____.
Numerical answer — type the value.
Show answer
Answer: 125
Cayley's formula gives n⁽ⁿ⁻²⁾ labelled trees on n vertices, so 5³ = 125. Check the exponent on the smallest case rather than trusting it: at n = 3 the formula gives 3¹ = 3, and there really are three labelled trees on three vertices, one for each choice of the middle vertex — which confirms n − 2 rather than n − 1. Four vertices give 4² = 16. Note what is being counted: trees on labelled vertices, where relabelling produces a different tree. The number of unlabelled tree shapes on five vertices is 3, a much smaller and unrelated count, and a question is always explicit about which it wants.
A 3-regular simple graph has 6 vertices. The number of its edges is _____.
Numerical answer — type the value.
Show answer
Answer: 9
The degree sum is 6 × 3 = 18, and the handshaking lemma says that equals 2|E|, so |E| = 9. The general form nk/2 is the one to carry, and it does double duty: it counts the edges when nk is even and proves non-existence when nk is odd. A 3-regular graph on 5 vertices would need 15/2 edges, which is why the earlier question in this chapter had no such graph. Both K₃,₃ and the prism graph are 3-regular on six vertices with nine edges, so the count does not determine the graph — a question asking how many such graphs is a harder and different question from this one.