Graph Theory Terminology

Degree of a vertex

Number of edges connected to it

Loop in graph theory

Counts as 2 degrees but 1 in an adjacency matrix.

Connected graph

No isolated vertices or separate parts

Bridge

An edge whose removal disconnects the graph.

Isolated vertex

A vertex with a degree of 0.

Multiple edges

Several edges connecting the same two vertices.

Simple graph

A graph with no loops or multiple edges.

Complete graph

Every pair is joined and there are one less edges than there are verticies

Subgraph

Part of a graph with no extra vertices or edges.

Sum of degrees formula

2 × number of edges.

Adjacency matrix

Square matrix where entry (m, n) is the number of edges joining vertices; symmetric.

Adjacency matrix (directed graphs)

Entry = arcs from row to column vertex; not necessarily symmetric.

Planar graph

A graph that can be drawn with no edges crossing.

Euler's formula for planar graphs

v + f − e = 2 (vertices + faces − edges = 2) for connected planar graphs.

Walk (graph theory)

A sequence of edges linking vertices.

Trail

A walk with no repeated edges (closed trail is a circuit).

Path (graph theory)

A walk with no repeated edges or vertices (closed path is a cycle).

Eulerian graph

A closed trail using every edge ⇔ connected with all vertices even.

Semi-Eulerian graph

An open trail using every edge ⇔ connected with exactly two odd vertices.

Hamiltonian cycle

A cycle visiting every vertex once and returning to the start.

Semi-Hamiltonian graph

An open path (Hamiltonian path) visiting every vertex once with no return.

Weighted graph vs Network

Weighted graph has edge weights; if physical quantities, it is a network.

Weight of a walk

The sum of the edge weights travelled.

Number of edges formula

n(n − 1) / 2.