Graphs/Definitions

Dietel Chapter 1: Graph Definitions and Concepts

Outline:

• Definitions
• graph,
• degree,
• path,
• cycle,
• connectivity,
• tree, forest,
• k-partite,
• contraction,
• Euler tours

Graph definitions

A graph G consists of a set of nodes (vertices) V and edges E, denoted $ G(V,E) $

Vertex set on graph G is denoted $ V(G) $

Edge set on graph G is denoted $ E(G) $

Number of vertices in a graph is called the order and is denoted $ |G| $

Number of edges in a graph is denoted $ \|G\| $

Vertex $ v \in V $ and edge $ e \in E $ are incident if the edge connects to the vertex.

Set of all edges at a particular vertex v is denoted $ E(v) $

Two vertices x, y are adjacent on a graph if there is an edge with endpoints x and y

If all vertices are pairwise adjacent, the graph is complete

For two graphs $ G = (V,E) $ and $ G' = (V',E') $, the graphs are isomorphic if there exists a bijection from V to V' that preserves adjacency (i.e., $ xy \in E $ iff $ f(x)f(y) \in E' $).

If we have two graphs G and G', we say that G' is a subgraph of G if $ V' \subseteq V $ and $ E' \subseteq E $

A subgraph G' is a spanning subgraph of G if all V' spans all of G (if V' = V)

Degree definitions

Set of neighbors of a vertex v is denoted $ N(v) $

Degree of a vertex v is denoted $ d(v) $ and is equal to the number of edges $ |E(v)| $ at v

Vertex of degree 0 is isolated

A graph G where all of the vertices have the same degree, k, is called k-regular (or, just regular).

The minimum degree of G is $ \delta(G) = \min \left( d(v) \mid v \in V \right) $

The maximum degree of G is $ \Delta(G) = \max \left( d(v) \mid v \in V \right) $

The average degree of G is given by the expression $ d(G) = \dfrac{1}{|V|} \sum_{v \in V} d(v) $

Ratio of edges to vertices on a graph is $ \epsilon(G) = \dfrac{|E|}{|V|} $

If we define edges as having two endpoints, then adding up the degrees of all vertices will lead to twice the number of edges. Mathematically: $ |E| = \dfrac{1}{2} \sum_{v \in V} d(v) = \dfrac{1}{2} d(G) |V| $

This leads to the identity $ \epsilon(G) = \dfrac{1}{2} d(G) $ and the theorem that the number of vertices of odd degree in a graph must always be even. Proof: if the number of vertices of odd degree were odd, the sum of degrees would be odd, contradicting the fact that the sum of degrees equals $ 2|E| $ (an even number).

Path and Cycle Definitions

A path P on a graph G is a non-empty graph that contains vertices and edges that are in G: $ V = \{ x_0, x_1, x_2, \dots, x_k\} $ and $ E = \{ x_0 x_1, x_1 x_2, \dots, x_{k-1} x_k \} $

A path is usually referred to by the sequence of vertices it visits, or as a path "from/between x_0 to x_k"

Independent paths are paths containing no common (internal) vertices. Independent paths may share endpoints though.

We can denote parts of a path using special notation: if a path $ P = x_0 \dots x_{k} $, then the following notation is used to denote only a part of that path:

$ \begin{align} P x_i = x_0 \dots x_i \qquad 0 \leq i \leq k \\ x_i P = x_i \dots x_k \\ x_i P x_j = x_i \dots x_j \end{align} $

We can also connect paths using unions, or by using more shorthand:

$ P x \bigcup x Q y \bigcup y R = P x Q y R $

A cycle C consists of a path whose final edge connects the last node to the first node. Given a path $ P = x_0 \dots x_{k-1} $ the cycle is then $ C = P + x_{k-1} x_0 $

A k-cycle is denoted $ C^k $ and is a cycle of length k.

The girth of a graph is the length of the shortest cycle in the graph. The circumference of a graph is the maximum length of a cycle in the graph.

The distance of two vertices x and y is the length of the shortest path from x to y $ d_G(x,y) $.

A vertex is central if greatest distance from any other vertex is as small as possible. This minimum distance is the radius of the graph G. Formally:

$ rad(G) = \min_{x \in V(G)} \max_{y \in V(G)} d_G(x,y) $

Note that the radius of a graph is different from the minimum/average degree.

Connectivity

A graph is connected if any two arbitrary vertices are connected.

If the graph is directed, a connected graph means that for any two arbitrary vertices u and v, there is an edge connecting u to v or v to u. A strongly connected graph means that for any two arbitrary nodes u and v, there is an edge connecting u to v and another edge connecting v to u.

Suppose we have two sets of vertices A and B, and a third set of vertices X. Further suppose that any path that connects a vertex from A to a vertex from B contains a vertex from X. Then we say that X separates the vertex sets A and B.

A subgraph of G that is maximally connected (contains every vertex in G) is a component of G. If a component is connected, it is always non empty.

Vertex connectivity: A graph G is k-connected if $ |G| > k $ and $ G - X $ is connected for every set $ X \subseteq V $ with $ |X| < k $. In other words, no two vertices of G are separated by fewer than k vertices. The maximum value of k such that G is k-connected is the connectivity of G and is denoted $ \kappa(G) $.

Edge connectivity: A graph G is l-edge-connected if $ G - F $ is connected for every set $ F \subseteq E $ with $ |F| < l $. That is, the removal of fewer than l edges never disconnects the graph. The edge connectivity of G, denoted $ \lambda(G) $, is the greatest integer l such that G is l-edge-connected.

Theorem due to Mader 1972: Every graph of average degree at least 4k has a k-connected subgraph. (Can prove inductively.)

Trees and Forests

Acyclic graphs are called forests. Connected forests are called trees.

A connected graph with n vertices is a tree if and only if it has n-1 edges.

We can (but don't have to) pick a particular node to be special - the root of the tree. In that case it is a rooted tree. When we pick a root r, this imposes a tree-order on the vertices: we say $ x \leq y $ if the unique path from the root r to y passes through x (that is, x lies on the path rTy).

A rooted tree T is called normal if any two vertices that are adjacent in the graph are comparable under this tree-order. Every connected graph has a normal spanning tree. (For infinite graphs, the existence of a normal spanning tree requires the graph to be countable; uncountable complete graphs, for example, have none.)

Bipartite Graphs

A k-partite graph is a graph where the set of vertices V can be partitioned into k classes, such that every edge that starts in one partition will end in a different partition.

If we can select any two vertices from two different classes and they are connected, the k-partite graph is complete.

Bipartite graphs cannot contain cycles of odd lengths. This is always true, so that we can identify bipartite graphs using this property: a graph is bipartite iff it contains no odd cycle.

Edge Contraction

Given a graph G with vertex set V and edge set E. Let e be an edge connecting vertex x to vertex y. Then $ G/e $ denotes the graph obtained by contracting the edge into a new vertex, which is now adjacent to all former neighbors of x and y.

Euler Tours

Main article: Graphs/Euler Tours

An Euler tour is a closed walk on a graph that traverses each edge of the graph exactly once. Some graphs have an Euler tour (and are called Eulerian), other graphs are not.

A connected graph is Eulerian if and only if every vertex has even degree. This is because any vertex appearing k times in an Euler tour must have degree 2k.

Other Definitions

A hypergraph is a pair of disjoint sets (V,E) where the elements of the edge sets are non-empty subsets of V. (That is, a given edge e in the set E can connect multiple vertices.)

A directed graph is a pair of disjoint sets (V,E) along with two maps: the init map from V to E (denoting the initialization or origin of the directed edge) and the term map from V to E (denoting the termination of the directed edge).

A multigraph is a pair of disjoint sets (V,E) together with a map from E to V or to V^2. In other words, it is a graph in which we can have edges that begin and end at the same vertex.