7.02 | graph theory

what is a graph?

a set of vertices connected by arcs.

what is a vertex/node?

a point in the graph.

what is an arc/edge?

a line or curve with a vertex at each end.

what does it mean for two vertices to be adjacent?

if there is an arc with these vertices at its ends.

what is a loop?

an arc that directly connects to itself.

what is an indirect connection between two vertices?

passes through other vertices and involves more than one arc.

what defines a simply connected graph?

both simple (exactly one arc between any two adjacent vertices and no loops) and connected (possible to get from any vertex to any other).

what is the degree of a vertex?

the number of arcs incident on that vertex.

what is the relationship between the sum of vertex degrees and the number of arcs in a graph?

the sum of the vertex degrees is twice the number of arcs.

what is a tree?

a simply connected graph with the minimum possible number of arcs.

what is a subgraph?

formed using some of the arcs of the graph together with the vertices that these arcs connect, and possibly some other unconnected vertices.

what is a walk?

a connected subgraph consisting of a set of arcs where the end vertex of one arc is the start vertex of the next.

what is the difference between a trail and a walk?

a walk can repeat edges, whereas a trail must have distinct edges (cannot be repeated).

what is a path?

a trail in which no vertex is repeated.

what is a cycle?

a closed path, meaning it has an extra arc that joins the end vertex back to the start vertex.

what is a complete graph?

a simply connected graph with the maximum possible number of arcs.

what is a bipartite graph?

a graph where its vertices can be partitioned into two sets so that every arc joins a vertex from one set to a vertex in the other set.

what is a complete bipartite graph?

a simply connected bipartite graph with the maximum possible number of arcs.

what characterises an eulerian graph?

no odd vertex degrees and is traversable with the same start and finish point.

what is a semi-eulerian graph?

has exactly two odd vertex degrees and is semi-traversable.

what defines a hamiltonian graph?

it contains a cycle that passes through every vertex exactly once, apart from the start and finish being the same.

what does ore's theorem state?

for a simply connected graph, if the sum of the vertex degrees for every pair of non-adjacent vertices is at least the number of vertices, then the graph is hamiltonian.

what is a digraph?

a graph with directed arcs.

what is euler's relation for planar graphs?

for any planar graph, the relation states that V - E + F = 2, where V is the number of vertices, E is the number of edges, and F is the number of faces.

what is an adjacency matrix?

it shows the number of arcs that directly join pairs of vertices.

what is a network?

a weighted graph, meaning that the arcs have numerical values attached to them.

what is a planar graph?

any graph that can be drawn with no arcs crossing (can be drawn as one layer).

what is a subdivision?

inserting a vertex of degree 2 into an arc.

what is a contraction?

removing an arc from a graph and merging the two vertices that it previously joined.

what is kuratowski’s theorem?

a necessary and sufficient condition for a finite graph to be planar is that it does not contain a subgraph that is a subdivision of K5 or K3,3