Graph Theory: every key term you need (+ practice quiz)
25 flashcard terms for Discrete Mathematics Topic 7, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A structure made of vertices together with edges joining pairs of them. It records only which pairs are connected, so drawings that look different may represent the same graph.
Simple graph
A graph with no loops and no repeated edges between the same pair of vertices. Most named results assume this, and multigraphs need separate statements.
Directed graph
A graph whose edges have an orientation, so an edge from one vertex to another need not be matched by one in the reverse direction. Vertices then have separate in and out degrees.
Weighted graph
A graph whose edges carry numerical values representing cost, distance or capacity. Shortest path and minimum spanning tree problems are stated on such graphs.
Degree of a vertex
The number of edges meeting a vertex, with a loop counted twice. Degrees are the most basic invariant available for distinguishing two graphs.
Handshaking theorem
The sum of all vertex degrees equals twice the number of edges, because each edge contributes to exactly two degrees. It forces the number of odd degree vertices to be even.
Adjacency matrix
A square array whose entry records whether or how many edges join two vertices. Powers of the matrix count walks of a given length between each pair.
Adjacency list
A representation storing for each vertex the collection of its neighbours, which is far more space efficient than a matrix for sparse graphs and speeds up neighbour scans.
Walk, trail and path
A walk is any sequence of adjacent vertices, a trail repeats no edge, and a path repeats no vertex. Each restriction is strictly stronger than the last.
Cycle in a graph
A closed path returning to its start with no repeated vertices along the way. A graph with no cycles at all is called acyclic.
Connected graph
A graph in which some path joins every pair of vertices. A disconnected graph splits into maximal connected pieces called components.
Connected component
A maximal set of vertices any two of which are joined by a path, together with the edges among them. Search algorithms find components in linear time.
Complete graph
A simple graph in which every pair of distinct vertices is joined by an edge, so a graph on n vertices has n choose two edges and every vertex has degree n minus one.
Bipartite graph
A graph whose vertices split into two sets with every edge running between the sets. A graph is bipartite exactly when it contains no cycle of odd length.
Subgraph
A graph formed from a subset of the vertices and a subset of the edges among them. An induced subgraph keeps every original edge between the chosen vertices.
Graph isomorphism
A relabelling of vertices that turns one graph into another while preserving adjacency. Isomorphic graphs share every structural invariant, though matching invariants do not prove isomorphism.
Euler circuit
A closed walk using every edge exactly once. A connected graph has one exactly when every vertex has even degree, which is the condition Euler established.
Euler path
A walk using every edge exactly once without returning to its start. A connected graph admits one exactly when it has precisely two vertices of odd degree.
Hamilton cycle
A cycle visiting every vertex exactly once. No simple characterisation is known, and deciding existence is computationally hard, in sharp contrast to the Euler condition.
Dirac condition
A sufficient condition for a Hamilton cycle: in a simple graph on at least three vertices where every vertex has degree at least half the vertex count, such a cycle exists.
Ore condition
A sufficient condition for a Hamilton cycle stating that the degrees of every nonadjacent pair sum to at least the number of vertices. It generalises the Dirac condition.
Planar graph
A graph that can be drawn in the plane with no edges crossing. Testing planarity is efficient, and the two minimal obstructions are the complete graph on five vertices and the complete bipartite graph on three and three.
Euler formula for planar graphs
For a connected planar drawing, the vertex count minus the edge count plus the face count always equals two, regardless of how the graph is drawn.
Graph colouring
An assignment of colours to vertices so that adjacent vertices differ. The smallest number of colours needed is the chromatic number, and bipartite graphs are exactly those needing at most two.
Four colour theorem
The result that every planar graph can be properly coloured with four colours, first proved with extensive computer assistance and still without a short human verifiable argument.