Terminology and notation

Terminology and notation

Basics of Graphs

  • A graph is a collection of points (called vertices) and lines connecting those vertices (called edges).
  • Graphs can be directed (edges have a direction) or undirected (edges do not have a direction).
  • The degree of a vertex is the number of edges touching it. In a directed graph, we distinguish between the in-degree (number of edges coming in) and out-degree (number of edges going out).
  • A loop is an edge that starts and finishes at the same vertex.
  • A simple graph is a graph with no loops or repeated edges.
  • A graph is connected if there is a path from every vertex to every other vertex.

Graph Notation

  • The order of a graph, denoted as G , is the number of vertices it contains.
  • The size of a graph, denoted as   G   , is the number of edges it contains.
  • We often denote a graph as G(V, E), where V is the set of vertices and E is the set of edges.
  • A subgraph H(V’, E’) of G(V, E) has V’ as a subset of V and E’ as a subset of E.
  • A complete graph on n vertices, denoted by K_n, is a simple graph with an edge between every distinct pair of vertices.

Trees and Forests

  • A tree is a connected graph with no cycles.
  • A forest is a graph without cycles, but it might not be connected — it could be a collection of several disjoint trees.
  • A vertex of degree 1 in a tree or forest is called a leaf.
  • Every tree with two or more vertices has at least two leaves.

Paths and Cycles

  • A path in a graph is a sequence of unique vertices in which successive vertices are connected by edges.
  • A cycle is a path that starts and ends at the same vertex, with no other repeated vertices or edges.
  • A graph is cyclic if it contains at least one cycle, and acyclic if it contains no cycles.
  • A Hamiltonian cycle is a cycle that visits each vertex exactly once (not including the starting and ending vertex, which are the same). A graph containing a Hamiltonian cycle is called a Hamiltonian graph.
  • An Eulerian cycle is a cycle that includes each edge exactly once. A graph is Eulerian if it contains an Eulerian cycle.