Graph Theory: Definitions and Properties

• A graph G is defined as a pair (V(G), E(G)), where V(G) is a nonempty set of vertices and E(G) is a family of two-element subsets of V(G) called edges.
• V(G) is the vertex set of G.
• E(G) is the edge set of G.
• Graphs can be represented by diagrams, with vertices as points and edges as lines or arcs.
• The representation isn't unique; the positions of vertices and edges don't matter.
• An edge {u, v} can be written as uv.
• If e = uv is an edge, then u and v are adjacent vertices, and u and e are incident.
• Two distinct edges sharing a vertex are adjacent edges.
• A graph is finite if the vertex set is finite; otherwise, it's infinite.
• Order of a graph G refers to the number of vertices, denoted by v(G).
• Size of a graph G refers to the number of edges, denoted by ɛ(G).
• A simple graph is the term often used in other books for the graph in this definition.
• Multiple edges are when two edges connect the same two vertices.
• A loop is an edge joining a vertex to itself.
• A multigraph has multiple edges but no loops.
• A pseudograph has both loops and multiple edges.
• A directed graph (digraph) D is a pair (V(D), E(D)),
• V(D) is a nonempty set of vertices.
• E(D) is a family of ordered pairs of distinct vertices called arcs.
• An oriented graph is a digraph with no symmetric pair of arcs.

Special Types of Graphs

• An empty graph has no edges.
• A complete graph of order n ≥ 1, denoted by Kn, has n vertices, with every two distinct vertices being adjacent.
• The graph K₁ is called the trivial graph.
• The graph K3 is often called the triangle.
• A path of order n ≥ 2, denoted by Pn, has vertices V(Pn) = {v1, v2, ..., vn} and edges E(Pn) = {ViVi+1: 1≤ i ≤ n-1}.
• A cycle of order n ≥ 3, denoted by Cn, has vertices V(Cn) = {v1, v2, ..., vn} and edges E(Cn) = {ViVi+1: 1 ≤ i ≤ n −1} ∪ {V1Vn}.
• A fan of order n ≥ 3, denoted by Fn, has vertices V(Fn) = {v0, v1, ..., vn-1} and edges E(Fn) = {ViVi+1: 1 ≤ i ≤ n − 1} ∪ {VoVk: 1 ≤ k ≤n-1}.
• A wheel of order n ≥ 4, denoted by Wn, has vertices V(Wn) = {v0, v1, ..., vn-1} and edges E(Wn) = {ViVi+1: 1 ≤ i ≤ n − 1} ∪ {vovk: 1 ≤ k ≤ n −1} ∪ {V1Vn-1}.
• Two graphs G and H are isomorphic (G ≅ H) if there is a one-to-one mapping φ from V(G) onto V(H) that preserves adjacency.
• A mapping φ: V(G) → V(H) is one-to-one, onto, and u and v are adjacent in G if and only if φ(u) and φ(v) are adjacent in H.
• This mapping φ is called an isomorphism.
• An invariant of a graph G is a number associated with G that is the same for any graph isomorphic to G.
• Order and size are graph invariants.
• A subgraph H of a graph G is a graph having all its vertices and edges in G. This is written as H ⊆ G.
• A spanning subgraph contains all vertices of G.
• Given S, a nonempty subset of V(G), the subgraph 〈S〉G of G induced by S has vertex set S.
• The edge set includes edges of G incident with two elements of S, making 〈S〉G the maximal subgraph of G with vertices in S.
• A graph G is connected if every pair of points can be joined by a path.
• If not every pair of points can be joined by a path, we say that G is disconnected.
• A maximal connected subgraph of G is called a component of G.
• The distance between u and v is denoted by d(u, v), is the length of a shortest path joining the vertices. If there is no such path, the distance is infinite.
• For any u,v,w∈V(G), the distance is a metric: d(u,v)≥0, d(u, v) = 0 if and only if u = v, d(u,v) = d(v,u), d(u,w) ≤ d(u,v) + d(v,w).
• A shortest u-v path in G is called a geodesic.
• The diameter of G, denoted by diam(G), is the length of any longest geodesic.