Note: all definitions are assumed to be in the context of undirected graphs unless specified.
def
Graph: a diagram constituted by points(vertices) and lines(edges) that connects some(possibly no) pairs of those points. It can be viewed as a visualization of the relationships between various components in a network.
def's
The number of vertices of a graph G is the order of G, and the number of edges of G is the size of G.
Note: A graph can be described as \(G=(V, E)\), where V is the set of vertices and E is the set of edges in G.
The animation below is interactive: left-click to create a vertex; drag from a vertex to another vertex to create an edge.
def
The number of edges connected to a vertex v is the degree of v, denoted as \(deg(v)\).
For example, every vertex of the graph in the image above has a degree of 4.
def
If a graph G has no loops(edges starting and ending at the same vertex) and no multiple edges between the same pair of points, then G is simple.
def
If a sequence of distinct edges \(e_1e_2...e_k\) is such that one can walk continuously through them, then it's a trail.
Note: an edge can also be expressed in terms of the vertices it connects(e.g \(v_1v_2\) is the edge that connects vertices \(v_1\) and \(v_2\)).
def
A walk is similar to a trail, except all edges need not be distinct.
The animation below is interactive: click an edge to indicate a part of a walk. A green border indicates the most recent vertex passed by a walk. Note: this animation doesn't allow repeated edges, although a walk can, by definition, have them.
def
A trail that doesn't touch any vertex twice is a path.
def
A trail using all edges of G is an Eulerian trail of G.
def
A trail that ends at the starting vertex is a closed trail.
def
A closed trail that doesn't touch any vertex twice is a cycle.
def
A cycle or path including all vertices of G is a Hamiltonian cycle or path of G.
def's
A graph with an empty edge set is an empty graph. A graph with an empty vertex set and an empty edge set is a null graph. A graph with one vertex(i.e., a singleton vertex set) and an empty edge set is a trivial graph.
def's
If ab(a, b are vertices) is an edge in a graph, then a and b are adjacent. Similarly, if A and B are edges in a graph such that A and B are both incident at vertex a, then A and B are adjacent.
def
Let \(G=(V(G), E(G)), H=(V(H), E(H)).\) If \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\), then H is a subgraph of G(\(H \subseteq G\)).(the symbol means something is a subset of something)
def's
H is: a proper subgraph of G if \(V(H) \subset V(G)\) and/or \(E(H) \subset E(G)\); a spanning subgraph if \(V(H) = V(G)\) and \(E(H) \subseteq E(G)\); an(vertex) induced subgraph if \(H \subseteq G\) and for any pair of vertices \((x,y)\) of G, if both x and y are in H, then all of the edges connecting x and y in G are also in H.
def's
If graph G is such that for any two vertices x and y, one can find a path from x to y, then G is connected. If G isn't connected, let k be the smallest integer so that G can be obtained as a union of k connected (sub)graphs. Then, G has k connected components.
def's
The distance between two vertices \(v_1, v_2\) in a graph is the length of the shortest path between them. This path is the geodesic between \(v_1\) and \(v_2\).
def
A path graph is a graph whose vertices can be listed in the order \(v_1, v_2,..., v_n\) such that all its edges are in the form \(v_iv_{i+1}\) where \(i=1,..., n-1\).
def
A cycle graph(or simply cycle) is a graph that consists of a single cycle. The length of a cycle graph is the number of its vertices or edges, and a cycle graph of length n is denoted as \(C_n\).
def
A complete graph is a simple undirected graph in which every distinct pair of vertices is connected by a unique edge. A complete graph on n vertices is denoted as \(K_n\).
def
The complement of a graph G, denoted as \(\bar G \), is a graph that has the same vertex set as G and for all pairs of distinct vertices u, v in G, uv is an edge of \(\bar G \) if and only if uv is not an edge of G.
def's
A graph G is regular if and only if each vertex has the same degree. A graph G is irregular if and only if all of its vertices have distinct degrees.
The animation below is interactive: left-click to create a vertex; drag from a vertex to another vertex to create an edge.
def
The hypercube graph on n vertices(denotes as \(Q_n\)) is the graph formed by the vertices and edges of an n-dimensional hypercube. In particular, \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges.
def
Let G be a graph on n vertices. Then, \(d_1d_2...d_n\) is a degree sequence of G if and only if the vertices of G can be labeled as \(v_1, v_2,..., v_n\) such that \(deg(v_i)=d_i\) for all \(i=1, 2,..., n\).
Conventionally, \(d_i \geq d_{i+1}\) for \(i=1, 2,..., n\).def
Graphs G and H are isomorphic if there is a one-to-one correspondence between the vertices of G and the vertices of H such that the number of edges between any pair of vertices in G is equal to that between their corresponding vertices in H.
More formally, G and H are isomorphic if there is a bijection \(f \colon V(G) \longrightarrow V(H)\) such that the number of edges between any vertices \(X\) and \(Y\) in G is equal to that of \(f(X)\) and \(f(Y)\) in H.
def
An automorphism of a graph G is an isomorphism between G and itself.
def
A graph in which each edge is assigned a direction is a directed graph. Sometimes it's called a digraph.
def
A digraph G is strongly connected if for all vertices a and b in G, there is path from a to b and vice versa.
def's
The indegree of a vertex of a digraph is the number of edges ending in that vertex. The outdegree of a vertex of a digraph is the number of edges starting in that vertex.
def
A digraph is balanced if the indegree is euqal to the outdegree for each vertex.
def
If each edge of a complete graph is assigned with a direction, the resulting digraph is called a tournament.
def
A tournament T is transitive if the fact that \(ij, jk \in E(T)\) implies \(ik \in E(T)\).
$$\text{Schur-Horn theorem}$$
$$\text{Let}$$ $$\{d_i\}, \{\lambda_i\}, i \in \{1,..., n\}$$ $$\text{be two sequences of reals, arranged in a non-increasing order.}$$ $$\text{Then, there is a Hermitian matrix with diagonal entries}$$ $$\{d_i\}$$ $$\text{and eigenvalues}$$ $$\{\lambda_i\}$$ $$\text{if and only if}$$ $$\sum_{i=1}^k d_i \leq \sum_{i=1}^k {\lambda_i}, \forall k \in \{1,..., n-1\}$$ $$\text{and}$$ $$\sum_{i=1}^n d_i = \sum_{i=1}^n {\lambda_i}.$$
Last updated: 7/11/2023