Definitions [1]

General Properties 1.1

1.1.6 Complete graph: a graph with the maximum possible size for a graph of order n. For a complete graph, every pair of vertices is adjacent.

1.1.5 Neighboring vertices: if e=uv is an edge of G, then u and v are joined by e and are neighbors. They are also called incident with each other.

1.1.4 Nontrivial graph: a graph with an order of at least two.

Subgraphs 1.2

1.2.4 Induced subgraph: a subgraph H⊆G which possesses the same edges as G, but only for the vertices V(H)⊆V(G), which might not be the full vertex set of the graph G.

1.2.2 Proper subgraph: consider a subgraph H⊆G. If G contains at least one vertex or edge not in H, then H is a proper subgraph of G.

1.2.1 Subgraph: consider a graph G, a subset of its vertices V(H)⊆V(G), and a subset of its edges E(H)⊆E(G). The graph H is a subgraph of G.

Traversing Graphs 1.3

3.12 Face: a space enclosed by a cycle. The space outside of a graph is also defined as a face.

1.3.11 Diameter: the diameter diam(G) is the greatest distance between any pair of vertices in the connected graph G.

1.3.10 Distance: given vertices u and v, the distance d(u,v) is the smallest length of any u-v path in G. This path is called a geodesic.

1.3.9 Cycle: a circuit which does not repeat any vertices except for the first and last. An odd cycle is a cycle with an odd length, an even cycle is a cycle with an even length, and a k-cycle is a cycle of length k.

1.3.7 Path: a walk in which no vertex is traversed more than once.

1.3.6 Trail: a walk in which no edge is traversed more than once.

1.3.1 Walk: a sequence of vertices starting with u∈G and ending with v∈G such that consecutive vertices are adjacent.

Connectedness 1.4

1.4.4 Component: a connected subgraph of G which is not a proper subgraph of any other subgraph of G. Alternatively, this is a connected subgraph H⊆G (connected within itself) which is not connected to any other subgraph in G.

1.4.2 Connected graph: a graph for which every pair of vertices is connected.

1.4.1 Connected vertices: if G contains a path from vertex u to vertex v, then u and v are connected vertices.

Common Types of Graphs 1.5

1.5.11 Oriented graph: a digraph without any pairs of vertices u and v connected by an equal number of edges with opposite directions.

1.5.10 Digraph: a set of vertices together with a set of edges defined by ordered pairs of vertices (called directed edges or arcs). Given a directed edge (u,v), the vertex u is called adjacent to v and the vertex v is called adjacent from u. The vertices u and v are also said to be incident with the directed edge (u,v).

1.5.9 Weighted graph: a multigraph in which all multi-edges are replaced by single edges equipped with weights. The values of the weights are defined as the number of multi-edges between a given pair of vertices.

1.5.8 Pseudograph: a multigraph which allows one or more edges which joins a given vertex to itself (a loop or self-edge).

1.5.7 Multigraph: in a multigraph, more than one edge is allowed between any given pair of vertices (multi-edges).

1.5.6 Complete multipartite graph: a multipartite graph for which every vertex of a given partite set of the graph is adjacent to a vertex of another partite set of the graph.

1.5.5 Multipartite graph: a graph for which V(G) can be partitioned into k subsets such that, for every edge uv∈G, the vertices u and v belong to different partite sets. This does not mean that every vertex of a given partite set is adjacent to a vertex from another partite set. Multipartite graphs are also called k-partite graphs.

1.5.3 Complete bipartite graph: a bipartite graph for which vertex of U is adjacent to a vertex of W. This type of graph is denoted as K s,t , where s and t represent the number of vertices in the sets U and W respectively.

1.5.2 Bipartite graph: a graph for which the vertex sets of G can be partitioned into two subsets U and W (called partite sets), such that every edge connects a vertex of U to a vertex of W. Note that this does not mean every vertex of U is adjacent to a vertex of W.

Operations on Graphs 1.6

1.6.5 Transpose: given a digraph D, its transpose is the digraph R such that the direction of each arc in D is reversed.

1.6.4 Cartesian product: given two graphs G and A, their Cartesian product G⨯A has a vertex set for which every vertex of G⨯A is an ordered pair (u,v) where u∈V(G) and v∈V(A). Two distinct vertices (u,v) and (s,t) within G⨯A are adjacent if either u=s and vt∈E(H) or v=t and us∈E(G). Note that this method of constructing G⨯A requiresthe vertices of G and A to be labeled in a sequential manner (i.e. V(G)={g,g,…,g} and V(A)={a,a,…,a}) so that equivalences between vertices can be decided. In addition, the Cartesian product of graphs is commutative, that is G⨯A=A⨯G.

1.6.3 Join: given two graph G and A, their join G+A creates the union of the graphs with the added property that each vertex of G is adjacent to all the vertices of A and each vertex of A is adjacent to all the vertices of G (as such, G+A is a connected graph).

1.6.2 Union: given two graphs G and A, their union G∪A creates a disconnected graphwith a vertex set V(G)∪V(A) and an edge set V(G)∪V(A).

1.6.1 Complement: a graph’s complement Ḡ possesses the same vertices as G, but has an edge uv if and only if uv is not an edge of G.

Definitions [2]

Degrees 2.1

2.1.14 Graphical: a finite sequence of nonnegative integers is called graphical if it corresponds to some graph G.

2.1.13 Degree sequence: any list of the degrees found in some graph. Usually, degree sequences can be ordered in multiple ways.

2.1.11 Regular graph: a graph with δ(G)=Δ(G) is called regular. For regular graphs, all vertices have the same degree. The degree r of a regular graph’s vertices is used to classify the graph as r-regular.

2.1.10 Indegree: for a digraph D, the indegree id(v) is the number of vertices of D from which v is adjacent.

2.1.9 Outdegree: for a digraph D, the outdegree od(v) is the number of vertices of D to which v is adjacent.

2.1.6 Maximum degree: given a graph G, its maximum degree Δ(G) is the highest degree among the vertices of G.

2.1.5 Minimum degree: given a graph G, its minimum degree δ(G) is the lowest degree among the vertices of G.

2.1.4 Leaf: a vertex with a degree of one, also called an end-vertex.

2.1.1 Degree: the number of edges incident with a vertex v. This is equivalent to the number of vertices adjacent to v. The degree of v is often denoted as deg(v).

Irregular Graphs 2.2

2.2.5 Underlying graph: if all multi-edges in a multigraph M are replaced by single edges, the resulting graph is called the underlying graph of M.

2.2.4 F-irregular: a graph is F-irregular if all pairs of vertices have distinct F-degrees.

2.2.3 F-regular: a graph is F-regular if every pair of vertices has the same F-degree.

2.2.2 F-degree: for a nontrivial subgraph F⊆G and a vertex v∈G, the F-degree (denoted Fdeg) is the number of copies of F in G which contain v.

2.2.1 Irregular graph: a graph G with an order of at least two is called irregular if every pair of vertices u∈V(G) and v∈V(G) have distinct degrees.

Matrices and Edge Lists for Graphs 2.3

2.3.1 Adjacency matrix: given a graph G of order n, its adjacency matrix A=a ij is the n x n matrix defined below. Adjacency matrices of simple graphs are symmetric with zeros along the diagonal. Adjacency matrices of pseudographs may have some ones on the diagonal (which indicates self-edges). Adjacency matrices of multigraphs may have integer values greater than one (which indicate more than one edge between given pairs of vertices). Adjacency matrices of digraphs (specifically oriented graphs) are not symmetric (indicating directed edges).

2.3.2 Incidence matrix: given a graph G of order n and size m, its incidence matrix B=b ij is the n x m matrix defined below.

2.3.3 Edge list: a list of ordered pairs (u 1 ,v 1 ), (u 2 ,v 2 ), … , (u n ,u n ) which corresponds to all of the edges in a graph.

Definitions [3]

Isomorphic Graphs 3.1

3.1.4 Isomorphic to a subgraph: given unlabeled graphs G and H, if for any labeling ofthe vertices of H and G, the labeled graph H is isomorphic to a subgraph of the labeled graph G.

3.1.3 Isomorphic digraphs: digraphs D 1 and D 2 are isomorphic if there exists a bijective function ϕ which maps V(D 1 ) to V(D 2 ) such that the directed edge (u 1 ,v 1 )∈E(D 1 ) if and only if (ϕ(u 1 ),ϕ(v 1 ))∈E(D 2 ).

3.1.2 Isomorphic graphs: two graphs G and H are isomorphic if there exists a bijective function ϕ which maps V(G) to V(H) such that uv∈E(G) if and only if ϕ(u)ϕ(v)∈V(H). The bijective function ϕ is called an isomorphism. Isomorphic graphs are denoted as G≌H. Isomorphisms are also equivalence relations (and so possess the properties of equivalence relations). Note that isomorphic graphs possess the same structure, but might be drawn differently.

3.1.1 Equal graphs: a pair of graphs with the same vertex set and edge set.

Trees 3.2

3.2.8 Rooted tree: a tree T for which some vertex v∈T is designated as the root of T. When drawing rooted trees, the root is placed at the top and the other vertices at successively lower levels depending on their geodesic distance from the root.

3.2.7 Caterpillar: a tree with an order of at least three for which removal of its end-vertices would give a linear graph. In the case of caterpillars, this linear graph is called a spine.

3.2.5 Double star: a tree containing exactly two vertices that are not end-vertices.

3.2.2 Acyclic graph: a graph with no cycles. If an acyclic graph consists of more than one component, it is also called a forest.

3.2.1 Bridge: consider an edge e=uv of a connected graph G. If removing e from G gives a disconnected graph, then e is a bridge.

Minimum Spanning Tree Problem 3.3

3.3.4 Prim’s algorithm: an algorithm for finding a minimum spanning tree T of a connected weighted graph G with order n. To carry out Prim’s algorithm, first choose any vertex v∈G and an edge e 1 ∈G incident with v such that e 1 has the lowest weight among the edges incident with v. Add this edge to T. Continue adding edges (e 2 , e 3 , e 4 , … , e n-1 ) to T such that each edge has the minimum weight among the set of edges that possess exactly one vertex incident with an edge already selected.

3.3.3 Kruskal’s algorithm: an algorithm for finding a minimum spanning tree T of a connected weighted graph G. To carry out Kruskal’s algorithm, first choose any edge e∈G with the minimum weight among the edge set of G and mark eas an edge of T. Then choose another edge e∈G with the minimum weight among the remaining edge set of G and mark eas an edge of T. Next, choose a third edge e∈G such that adding einto the edge set of T does not create any cycles (emust still possess the minimum weight among the remaining edge set of G) and mark eas an edge of T. Continue this process with each new edge having the minimum weight among the remaining edge set and not creating any cycles until a spanning graph T has beenconstructed. The resulting graph is a minimum spanning tree of G.

3.3.2 Minimum spanning tree: given a connected weighted graph G, its minimum spanning tree is the spanning tree T for which the sum of its edge weights is the lowest value among all possible spanning trees of G. Finding a minimum spanning tree of a graph G is called the minimum spanning tree problem.

3.3.1 Spanning tree: given a connected graph G, a spanning tree is a spanning subgraph T⊆G that is also a tree.

Definitions [4]

Connectivity 4.1

4.1.14 k-edge-connected graph: a graph with λ(G)≥k (where k is a nonnegative integer), often denoted by K n .

4.1.13 Edge-connectivity: given a nontrivial graph G, the edge-connectivity λ(G) is the cardinality of a minimum edge-cut of G.

4.1.12 Minimum edge-cut: for an edge-cut X which is not minimal (of a connected graph G), there exists a proper subset Y⊂X that is a minimal edge edge-cut. An edge-cut of minimum cardinality is called a minimum edge-cut. Note that every minimum edge-cut is a minimal edge-cut, but not every minimal edge-cut is a minimum edge-cut.

4.1.11 Minimal edge-cut: an edge-cut X of a connected graph G is called minimal if no proper subset of X is an edge-cut of G.

4.1.8 Vertex-connectivity: the cardinality of a minimum vertex-cut of a graph. Vertex connectivity is also referred to as just connectivity and is denoted by κ(G).

4.1.7 Minimum vertex-cut: a vertex-cut of minimum cardinality in G (cardinality is the number of elements in a set).

4.1.5 Block: for a nontrivial connected graph G which is separable, a block is a nonseparable subgraph H⊆G such that H is not a proper subgraph of any other nonseparable subgraph in G.

4.1.4 Edge-disjoint subgraphs: two subgraphs are called edge-disjoint if they do not share any common edges.

4.1.3 Separable graph: a nontrivial connected graph which contains at least one cut-vertex.

4.1.2 Nonseparable graph: a nontrivial connected graph which does not contain any cut-vertices.

4.1.1 Cut-vertex: given a connected graph G, if the removal of a vertex v∈G turns G into a disconnected graph, then v is called a cut-vertex. (Note that vertex removal can be denoted by G – v). For a disconnected graph G, cut-vertices are defined as vertices for which removal would turn any component of G into two or more disconnected subgraphs of G (rather than a single disconnected subgraph of G).

Terms Relevant to Menger’s Theorem 4.2

4.2.4 Internally disjoint paths: a collection of u-v paths {P 1 ,P 2 ,…,P k } such that none of the paths possess common vertices with the exception of the vertices u and v.

4.2.3 Internal vertex: given a u-v path P, an internal vertex of P is a vertex w∈P such that w≠u,v.

4.2.2 Minimum u-v separating set: a u-v separating set S with minimum cardinality among all possible u-v separating sets of a graph.

4.2.1 Separation: a set of vertices S∈G separates two vertices u and v if G – S is a disconnected graph with u and v belonging to different components of G – S. The set S is called a u-v separating set.

Definitions [5]

Eulerian Graphs 5.1

5.1.3 Eulerian trail: an open trail which contains every edge of a graph G.

Hamiltonian Graphs 5.2

5.2.6 Spanning walk: a walk which visits every vertex of a graph at least once. Note that a Hamiltonian walk is a closed spanning walk of minimum length.

5.2.5 Petersen graph: a simple graph with ten vertices and fifteen edges, often used as a counterexample for various graph-theoretic problems.

Digraphs 5.3

5.3.11 Strongly connected digraph: if a digraph D contains both a u-v path and a v-upath for every pair of vertices u,v∈D. An orientation which converts a simple graph into a strongly connected digraph is called a strong orientation. Alternatively, a strongly connected digraph is a digraph for which every vertex can be visited by a single directed path.

5.3.9 Directed distance: given a digraph D and vertices u,v∈D, the directed distance d (u,v) is the length of the shortest u-v path in D. As with simple graphs, a u-v path of length d (u,v) is called a geodesic.

5.3.8 Directed cycle: a closed directed walk with a length of at least two.

5.3.7 Directed circuit: a closed directed trail with a length of at least two.

5.3.4 Directed walk: a sequence of vertices starting with u∈G and ending with v∈G such that consecutive vertices are adjacent and the walker proceeds in the direction of the arrows. The length of a directed walk is the number of arcs traversed. If no arc is repeated over a directed walk, then the directed walk is called a directed trail. If no vertex is repeated over a directed walk, then the directed walk is called a directed path.

5.3.3 Symmetric digraph: a digraph D for which every directed directed edge (u,v)∈G, there also exists a directed edge (v,u)∈G. Note that directed edges are also called arcs.

5.3.2 Subdigraph: a digraph H such that V(H)⊆G and E(H)⊆G where G is a digraph containing H.

5.3.1 Orientation of a graph: given a simple graph G, the orientation of G is a digraph generated by assigning a direction to each edge of G.

Digraph Tournaments 5.4

5.4.2 Transitive tournament: a tournament T for which the following statement holds. Whenever T has arcs (u,v) and (v,w), it also has an arc (u,w).

Theorems [1]

Theorem 1.8: the nontrivial graph G is a bipartite graph if and only if G does not contain odd cycles.

Theorem 1.7: if G is a disconnected graph, then its complement Ḡ is connected.

Theorem 1.6: the size of a complete graph of order n is given by n(n-1)/2.

Theorem 1.5: given a connected graph G with an order of three or more, G contains a pair of distinct vertices u and v such that G is connected to u and G is connected to v.

Theorem 1.4: given a graph G with an order of three or more and two distinct vertices u and v. If u is connected to G and v is connected to G, then G is a connected graph.

Theorem 1.3: if vertices u and v belong to different components of a disconnected graph, uv∉E(G).

Theorem 1.2: the vertices and edges of a trail, path, circuit, or cycle in a graph G form a subgraph H⊆G.

Theorem 1.1: if a graph G with a walk of length L, then G contains a path of length p≤L.

Theorems [2]

Theorem 2.1 handshaking lemma: given a graph G with a size of m, the sum of the degrees of the vertices is equal to 2m (or twice the total number of edges).

Theorem 2.3: given a graph G of order n and the relation below (in which u and v represent nonadjacent vertices), G is connected and diam(G)≤2.

Theorem 2.2: every graph has and even number of odd vertices.

Theorem 2.7: a non-increasing sequence of nonnegative integers s 1 , s 2 , … s n (where s 1 ≥1) is graphical if and only if the sequence below is graphical.

Theorem 2.6: for every graph H and every integer r≥Δ(G), there exists an r-regular graph G which contains H as an induced subgraph.

Theorem 2.5: given integers r and n such that 0≤r≤n-1, there exists an r-regular graph of order n if and only if either r or n is even.

Theorem 2.4: given a graph G of order n and δ(G)≥(n-1)/2, the graph G is connected.

Theorem 2.10: given a graph F with order k≥2 and a graph G which contains m copies of F as subgraphs, the equality below (involving the F-degree) is true.

Theorem 2.9 the party theorem: for any nontrivial simple graph, there exists a pair of vertices with the same degree. As such, no nontrivial simple graph is irregular.

Theorem 2.8: if a graph’s adjacency matrix A=a ij is raised to a power k, then the entry a ij k in row i and column j of A k is equal to the number of distinct v i -v j walks of length k within the graph.

Theorem 2.14 Euler’s formula: given a graph with V vertices, E edges, and F faces (recall that the space outside of a graph is counted as a face) that is drawn without edge intersections, the relation below is always true.

Theorem 2.13: given a connected graph G with an order of two or more, G is the underlying graph of an irregular multigraph or irregular weighted graph.

Theorem 2.12: given a nontrivial connected graph F, there exists an F-irregular graph if and only if Fdeg≠2.

Theorem 2.11: given a subgraph F with an even order and a graph G, the graph G has an even number of vertices with an odd F-degree.

Theorem 2.15: given an adjacency matrix A of a digraph D, the transposed matrix A T is the adjacency matrix of a digraph R such that R is the graph transpose of D.

Theorems [3]

Theorem 3.12: every connected graph contains at least one spanning tree.

Theorem 3.11: if T is a tree with order k and G is a graph with minimum degree δ(G)≥k–1, then T is isomorphic to some subgraph of G.

Theorem 3.10: given a graph G of order n and size, if G satisfies any two of the following properties, then G is a tree. (i) G is connected, (ii) G is acyclic, (iii) m=n–1.

Theorem 3.9: every forest of order n with k components has a size of n–k.

Theorem 3.7: every nontrivial tree has at least two end-vertices.

Theorem 3.6: a graph G is a tree if and only if every pair of vertices in G are connected by a unique path.

Theorem 3.5: an edge e∈G is a bridge if and only if e does not lie on any cycles of G.

Theorem 3.4: isomorphism is an equivalence relation on the set of all graphs and so isomorphism is reflexive (every graph is isomorphic to itself), symmetric (there exists an inverse for every isomorphism), and transitive (if G 1 ≌G 2 and G 2 ≌G 3 , then G 1 ≌G 3 ).

Theorem 3.3: two isomorphic graphs G and H possess the same structural properties. For instance, G is bipartite if and only if H is bipartite, G is connected if and only if H is connected, G contains a 3-cycle if and only if H contains a 3-cycle, etc.

Theorem 3.1: two graphs are isomorphic if and only if their complements are isomorphic.

Theorems [4]

Theorem 4.20: a nontrivial graph G is k-edge-connected if and only if G contains k edge-disjoint u-v paths for each pair of distinct vertices u,v∈G.

Theorem 4.19: given distinct vertices u and v in a graph G, the minimum number of edges in G which separate u and v equals the maximum number of edge-disjoint u-v paths in G for each pair of distinct vertices u,v∈

Theorem 4.18: given a k-connected graph G with k≥2, every k vertices of G lie on a common cycle of G.

Theorem 4.17: given a k-connected graph G and vertices k+1 distinct vertices of u,v 1 ,v 2 ,…,v k ∈G; there exist internally disjoint u-v i paths such that 1≤i≤k.

Theorem 4.16: given a k-connected graph G any set S of k vertices in G, if a new vertex w is created and joined to the vertices of S, then the resulting graph is also k-connected.

Theorem 4.15: a nontrivial graph G is k-connected for an integer k≥2 if and only if every pair of distinct vertices u,v∈G corresponds to at least k internally disjoint u-v paths in G.

Theorem 4.14 Menger’s theorem: given nonadjacent vertices u and v in a graph G, the minimum number of vertices in a u-v separating set equals the maximum number of internally disjoint u-v paths in G.

Theorem 4.10: for every positive integer n, there exists a k-edge-connected graph K n such that λ(K n )=n-1.

Theorem 4.9: every two distinct blocks B 1 and B 2 in a nontrivial connected graph have the following properties. (i) B 1 and B 2 are edge disjoint, (ii) B 1 and B 2 have at most one common vertex, and (iii) if B 1 and B 2 share a common vertex v, then v is a cut-vertex of G.

Theorem 4.8: an equivalence relation R can be defined on the edge set of a nontrivial connected graph G for edges e,f∈E(G) when e=f or e and f lie on a common cycle of G.

Theorem 4.7: given a graph G with an order of three or greater, G is nonseparable if and only if every two vertices lie on a common cycle.

Theorem 4.6: every nontrivial connected graph contains at least two vertices which are not cut-vertices.

Theorem 4.5: consider a nontrivial connected graph G and vertices u,v∈V(G). If v is the farthest possible vertex from u as measured by d(u,v), then v is not a cut-vertex of G.

Theorem 4.4: a vertex v of a connected graph G is a cut-vertex if and only if there exist vertices u and w (distinct from v) such that v lies on every u-w path of G.

Theorem 4.3: given a cut-vertex v in a connected graph G as well as vertices u and w that belong to distinct components of the disconnected graph G – v, the vertex v lies on every u-w path of G.

Theorem 4.2: given a connected graph G with an order of three or greater, if G contains a bridge, then G contains a cut-vertex.

Theorem 4.1: given a vertex v incident with a bridge within a connected graph G, v is a cut-vertex of G if and only if deg(v)≥2.

Theorems [5]

Theorem 5.1: a connected graph G contains an Eulerian trail if and only if every vertex of G has an even degree or exactly two vertices of G have odd degrees. In the case of a graph with exactly two vertices of odd degree, each Eulerian trail begins at one of the vertices with an odd degree and ends at the other vertex with an odd degree.

Theorem 5.2: the Petersen graph is non-Hamiltonian.

Theorem 5.3: given a Hamiltonian graph G, then every nonempty proper subset S of vertices in G satisfies the relation k(G – S)≤|S|, where k(G – S) is the number of components in the graph G – S and |S| is the cardinality of S.

Theorem 5.4: if a graph G contains a cut-vertex, then G is not Hamiltonian.

Theorem 5.5: given a graph G with an order n≥3, if deg(u)+deg(v)≥n for every pair of nonadjacent vertices u,v∈G, then G is Hamiltonian.

Theorem 5.6: given a graph G with an order n≥3 and deg(v)≥n/2 for every vertex v∈G, then G is Hamiltonian.

Theorem 5.7: given two nonadjacent vertices u and v in a graph G of order n such that deg(u)+deg(v)n, G+uv is Hamiltonian if and only if G is Hamiltonian. Note that G+uv denotes the graph G with a new edge between vertices u and v (which were formerly nonadjacent).

Theorem 5.8: given a graph G with an order n≥3, if the relation 1≤j≤n/2 holds for every integer j and the number of vertices in G with a degree of at most j is less than j, then G is Hamiltonian.