Vertices and edges — A graph consists of vertices, also called nodes, and edges joining them. The drawing's shape and edge lengths do not matter unless weights or geometry are part of the model. A crossing without a marked vertex is not automatically a junction; state which crossings represent connections.
Networks and digraphs — A weighted graph or network assigns a quantity such as distance, cost or time to each edge. A digraph has directed edges or arcs. Direction can restrict permitted travel even if an undirected sketch appears connected. A matrix and a drawing must represent the same weights and permitted directions.
Simple and multiple-edge models — A simple undirected graph has no loops (edges from a vertex back to itself) and at most one edge between a given pair of distinct vertices. A multigraph may have repeated edges and can represent repeated traversals in a route-inspection construction. State which model is used before applying a formula restricted to simple graphs.
Degree or valency — The degree, sometimes called the order of a node in this course, counts incident edge ends. A loop contributes two at its vertex because it has two ends there. The number of vertices is also called the order of a graph in wider terminology; distinguish node degree from graph size and algorithmic order.
The handshaking relation — For an undirected graph, the sum of all vertex degrees is 2E, because each edge contributes two ends. Consequently the number of odd-degree vertices is even. If degrees are 3,3,2,2, their sum is 10 and there are five edges. This identity is a useful consistency check, not a complete description of a graph.
Walks, trails and paths — A walk follows adjacent edges and may repeat edges and vertices. A trail does not repeat an edge; a path in the usual simple-path convention does not repeat a vertex. State the intended convention if a problem uses route informally. A closed walk returns to its start; this alone does not make it Hamiltonian or Eulerian.
Cycles and circuits — A simple cycle returns to its starting vertex without revisiting other vertices. An Eulerian circuit may revisit vertices while using every edge once. Some examination wording calls an Eulerian circuit an Eulerian cycle; retain the essential every-edge requirement rather than incorrectly imposing a no-repeat-vertex rule.
Connectivity — A connected undirected graph has a path between every pair of vertices. Disconnected graphs have separate components. Many route algorithms require connectedness, so satisfying a degree condition alone does not guarantee one route can traverse the entire graph. Isolated vertices also matter when the question requires visiting every vertex.
Trees and spanning trees — A tree is connected and has no cycle. A tree on n vertices has n − 1 edges. A spanning tree uses all vertices of the original connected graph while retaining only a connected cycle-free subset of its edges. It need not be minimum weight unless an optimisation algorithm establishes that.
Complete graphs — The complete simple graph K_n joins every pair of distinct vertices, so each vertex has degree n − 1 and it has n(n − 1)/2 edges. K_5 therefore has ten edges and degree four at every vertex. Complete does not mean all drawn edges have equal length or weight.
Adjacency and weight matrices — Use a declared vertex order for rows and columns. An undirected adjacency matrix is symmetric and, for a simple graph, has zero diagonal; off-diagonal 1 marks an edge. A weight matrix stores edge weights instead. Distinguish an absent edge from a zero-cost edge using the specified dash, infinity or other convention.
Eulerian and Hamiltonian properties
Eulerian criterion — A connected graph with at least one edge has a closed route using every edge exactly once if and only if every vertex has even degree. Each arrival can be paired with a departure. The route may pass through a vertex more than once; the restriction is on edge usage.
Semi-Eulerian criterion — A connected graph has an open every-edge-once trail with different endpoints if and only if exactly two vertices have odd degree. Start at one odd vertex and finish at the other. All intermediate arrivals and departures pair up. Do not choose arbitrary endpoints if they have even degree.
Neither Eulerian nor semi-Eulerian — A connected graph with four or more odd vertices has neither a closed nor an open all-edge-once trail. It can still have walks using every edge if repeated traversals are permitted. Adding repeated edges can change parity and is developed in route inspection; it does not change the original graph's classification.
Constructing and checking a trail — For edges AB, BC, CA, AD, DB, the degrees are A 3, B3, C2 and D2. The open trail A–C–B–D–A–B uses each of the five edges once, starting at A and ending at B. Write the edge list alongside a proposed route to check for omissions or accidental repeated edges.
Hamiltonian cycle — A Hamiltonian cycle visits every vertex exactly once before returning to the start. It is a vertex-visiting property, unlike Eulerian edge traversal. A graph may have one property, both or neither. Finding a Hamiltonian cycle is not achieved merely by checking whether all degrees are even.
Useful examples — A square with one diagonal has two odd vertices and is semi-Eulerian, yet its perimeter is a Hamiltonian cycle. K_4 has four vertices each of degree 3, so it is neither Eulerian nor semi-Eulerian but has a Hamiltonian cycle. K_5 has all degrees 4 and has both a Hamiltonian cycle and an Eulerian circuit.
Restrictions on Hamiltonian claims — A graph with a degree-one vertex cannot have a Hamiltonian cycle, since a cycle needs distinct entering and leaving edges there. A bridge is an edge whose removal disconnects the graph. A connected graph with a bridge cannot have a Hamiltonian cycle through all vertices on both sides of that bridge. These are useful obstructions; satisfying their converses does not prove a cycle exists.
Isomorphism and planarity
Graph isomorphism — Two graphs are isomorphic if there is a one-to-one mapping of vertices preserving adjacency. They may be drawn differently and use different labels. Equal vertex and edge counts and matching degree sequences are necessary checks, but not sufficient: the connections themselves must correspond under a single mapping.
A degree-sequence trap — A six-vertex cycle and two disjoint triangles both have degree sequence (2,2,2,2,2,2), yet one is connected and the other is not. They are not isomorphic. Matching node degrees alone does not establish isomorphism; compare components, cycles and neighbour relationships and then give a valid mapping when claiming equivalence.
Planarity is about a possible drawing — A planar graph can be drawn on a plane without edges crossing except at shared endpoints. A drawing with crossings does not prove nonplanarity because edges can be rerouted. Curved edges are allowed; distances, straightness and a particular original picture are not graph invariants in this question: they can change when the same graph is redrawn.
K4 can be redrawn — Draw a square A–B–C–D–A with both diagonals AC and BD. In that drawing the diagonals cross, but one can be placed outside the square while the other stays inside. All six edges remain and no crossing is needed, so K_4 is planar.All six K4 edges are retained: four perimeter edges, AC inside and BD around the outside. The corners along the curved or bent outside route are not extra graph vertices. A crossing in the usual square-with-diagonals drawing is therefore avoidable.
Faces and Euler's relation — In a connected planar embedding, regions of the drawing, including the unbounded outside region, are faces. Euler's relation is V − E + F = 2. A tree has one face and E = V − 1. Count the outside face; omitting it gives a false inconsistency.
Simple planar edge bounds — For a simple connected planar graph with V ≥ 3, E ≤ 3V − 6, using that every face boundary has at least three edge occurrences and each edge contributes to two face boundaries. A bipartite graph splits its vertices into two sets, with every edge joining different sets. For a simple bipartite planar graph with V ≥ 3, E ≤ 2V − 4 because there are no triangular cycles. These are necessary bounds, not sufficient planarity tests.
Standard nonplanar examples — K_5 has V = 5 and E = 10, exceeding 3V − 6 = 9, so it is nonplanar. K_3,3 has V = 6 and E = 9, exceeding its bipartite planar bound 2V − 4 = 8. Its ordinary bound is 12, illustrating why passing a weaker necessary test is not proof of planarity.
The Hamiltonian-cycle planarity algorithm
Start with a spanning cycle — For the specified planarity method, first find a Hamiltonian cycle and draw its vertices in that cyclic order around a circle. Draw the cycle on the circle. Every remaining edge is a chord that must be routed on either the inside or outside. If no Hamiltonian cycle is available, this particular method cannot be applied; that does not imply nonplanarity.
Conflicting chords — Two noncycle edges with four distinct endpoints interlace when their endpoints alternate around the Hamiltonian circle. Such a pair cannot both be drawn on the same side without crossing. They must be assigned opposite sides. Edges sharing an endpoint do not create this conflict merely by touching at that common vertex.
Propagate the side choices — Choose a remaining chord and assign it inside. Put every conflicting chord outside, then every chord conflicting with those inside, continuing until all constraints are assigned. A disconnected set of conflicts can start with either side. If a chord is forced both inside and outside, no compatible drawing exists for the Hamiltonian cycle.
Constructive success and contradiction — When the conflict assignments are consistent, draw each side's noninterlacing chords without crossings and retain every original edge. This gives a planar embedding. A contradiction demonstrates nonplanarity for this Hamiltonian graph: any embedding would have to place its spanning cycle as a closed boundary with each remaining edge wholly on one side.
A six-cycle contradiction — For the cycle A–B–C–D–E–F–A and chords AD, BE and CF, every pair of chords interlaces. If AD is inside, BE and CF must both be outside, but they also conflict with each other. The contradiction proves this graph, which is K_3,3 under a suitable bipartition, nonplanar.The perimeter is the Hamiltonian cycle A,B,C,D,E,F,A. Each pair of AD,BE,CF has alternating endpoints, so each pair would need opposite sides. Two sides cannot satisfy all three conflicts. The central crossing is not a vertex; this diagram displays the conflict, not a claimed planar embedding.
An auxiliary conflict graph — As an explanatory way to record the same method, make one auxiliary vertex for each chord and join two when they interlace. A consistent inside/outside assignment is a two-colouring of this conflict graph. An odd conflict cycle causes a contradiction. This is a bookkeeping aid for the specified chord procedure, not a substitute for showing the required original graph and assignments.
Communicating a graph argument — For an Eulerian claim state connectivity and odd-degree count; for Hamiltonian claims give a valid vertex cycle or a justified obstruction; for isomorphism give a mapping or invariant contradiction; for planarity give an embedding or a valid proof. A plausible sketch and an unchecked degree list are not enough for every type of claim.
Test yourself
50 questions · Random sets of 10. These quick checks support revision; practise longer explanations and justified judgements too.
Mr Kidman's Classroom
