Graph

consists of points (called vertices or nodes) which are connected by lines (edges or arcs)

Weighted graph / network

A graph where the edges have associated values (weights)

Vertex set

A, B, C, D, E, F, the vertices within a graph

Edge set

AD, AE, BA, BC, CE, CF, DE, EF, the edges within the graph (G)

Subgraph of G

A graph, each of whose vertices belong to the original graph (G) and each of whose edges belong to G. It is simply a part of the original graph.

Degree, Order, or Valency of a vertex

The no. of edges incident to the vertex

A: 3, B: 2 etc.

Even vertex

vertex with an even degree

Odd vertex

vertex with an odd degree

Walk

A route through a graph along edges and from one vertex to another (can be multiple vertices and edges)

Path

A walk where no vertex is visited more than once

Trail

A walk where no edge is visited more than once

Cycle

A walk where the end vertex is the same as the start vertex and no vertex is visited more than once

Hamiltonian cycle

A cycle which includes every vertex.

Connected graph

Where every vertex is connected, in some way, to the graph. (Vertices are connected when there is an arc connecting them)

Loop

Edge that starts and finishes at the same vertex

Simple graph

A graph with no loops and up to one arc connecting the same two vertex

Directed graph

Graphs where direction is associated to each arc, often shortened to digraph

The Handshake Lemma

Th sum of the degrees of the vertices is equal to 2x the number of edges, as a consequence the number of vertices must be even. This is known as Euler's Handshake Lemma.