Introduction to Discrete Mathematics

Loosely speaking, a graph is a collection of points called vertices and connecting segments called edges, each of which starts at a vertex, ends at a vertex and contains no other vertices beside these. More formally, we define the term as follows. A graph consists of two sets, a nonempty set \(V\) of points called vertices and a set \(E\) whose elements, called edges, are multisets of size two from \(V\text{.}\)

Each edge is associated with either one vertex which serves as both endpoints or two vertices as its endpoints. Technically, each edge is a multiset of the form \({\multiset{u,v}}\) where \(u,v\in V\text{.}\) We say that \(u\) and \(v\) are endpoints of the edge \(\multiset{u,v}\text{.}\) In an abuse of notation, it is customary to write \({\{u,v\}}\) even if \(u=v\text{.}\) In fact, we may abbreviate further and denote the edge by \({uv}\text{.}\) Note that the order in which the vertices of an edge are listed is irrelevant. That is, \(\multiset{u,v}=\multiset{v,u}\text{,}\) \(\{u,v\}=\{v,u\}\text{,}\) and \(uv=vu\text{.}\) If \(G\) is the graph associated with the vertex set \(V\) and edge set \(E\text{,}\) we write \({G=(V,E)}\text{.}\) It is worth pointing out that we assumed that \(V\) is nonempty, but \(E\) is allowed to be empty (i.e., the graph has no edges).

It is customary to represent a graph using visual representations, where each vertex is a dot and each edge is a connecting segment, not necessarily straight.

A simple graph is a graph in which each edge connects two distinct vertices and each pair of vertices is connected by at most one edge. Note that the graphs \(K_n, C_n, P_n, W_n\text{,}\) and \(Q_n\) are all simple graphs. A pseudograph (or multigraph) is like a graph but we allow multiple edges between a pair of vertices (i.e., \(E\) is a multiset instead of a set).

A simple graph \(G = (V,E)\) is bipartite if there is a partition of \(V\) into two nonempty sets \(V_1,V_2\) (i.e., \(V_1\neq \emptyset\text{,}\) \(V_2\neq \emptyset\text{,}\) \(V_1\cap V_2=\emptyset\text{,}\) and \(V_1 \cup V_2 = V\)) such that each edge of \(G\) connects a vertex in \(V_1\) and a vertex in \(V_2\text{.}\) The pair \((V_1,V_2)\) is called a bipartition of the graph.

The following theorem provides a nice characterization of bipartite graphs.

A bipartite graph with bipartition \((V_1,V_2)\) such that \(|V_1|=m\) and \(|V_2|=n\) is the complete bipartite graph \(K_{m,n}\) if it contains each edge \(\{u,v\}\) for every pair \(u \in V_1\) and \(v \in V_2\text{.}\) Note that \(K_{m,n}=K_{n,m}\text{.}\)

The next result is sometimes referred to as the Handshake Lemma. Do you see why?

Sometimes it is convenient to use the term even vertex or odd vertex to refer to a vertex whose degree is even or odd, respectively.

The degree sequence of a graph is the list of the degrees of the vertices of the graph in descending order. A finite list of nonnegative integers in descending order is graphic if it is the degree sequence of a simple graph.

One consequence of the previous theorem is that any sequence with an odd sum (e.g., 331) is not graphic. It turns out that if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs, and fill out the remaining even degree counts by self-loops. The question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can be solved by either the Erdös–Gallai theorem or the Havel–Hakimi algorithm. Unfortunately, this is beyond the scope of this course.

If \(G=(V,E)\) is a graph and \(S\subseteq V\text{,}\) the neighborhood of \(S\text{,}\) denoted \({N(S)}\) is the set of all vertices in \(V\) adjacent to at least one member of \(S\text{.}\) Of course, we can consider the neighborhood of a single vertex \(v\text{,}\) which is denoted \({N(v)}\text{.}\) A neighborhood of a single vertex does not include itself, and is more specifically the open neighborhood of \(v\text{.}\) It is also possible to define a neighborhood in which \(v\) itself is also included. This is called the closed neighborhood of \(v\text{,}\) sometimes denoted by \({N[v]}\text{.}\) Unless stated otherwise, a neighborhood is assumed to be open.

A matching (or independent edge set) in a graph \(G=(V,E)\) is a subset of edges \(M\subseteq E\) without common vertices. That is, a subset of the edges is a matching if each vertex appears as an endpoint in at most one edge of that matching. If \(M\) is a matching, a vertex is said to be matched if it is an endpoint of one of the edges in \(M\text{.}\) Otherwise, the vertex is called unmatched. We say that \(M\) covers a subset \(S\subseteq V\) if every vertex of \(S\) is matched by \(M\text{.}\)

We now explore a type of matching problem. Suppose we have a bipartite graph \(G=(V,E)\) with a bipartition \((V_1,V_2)\text{.}\) We want to match up each element \(v_1\in V_1\) with exactly one element \(v_2 \in V_2\) that is adjacent to it in \(G\) and that is not matched to any other element of \(V_1\text{.}\)

A total matching from \(V_1\) to \(V_2\) is matching that covers \(V_1\text{.}\) In other words, for each \(v_1\in V_1\text{,}\) there is a unique edge \(m\in M\) and a unique \(v_2\in V_2\) such that \(m\) is incident to \(v_1\) and \(v_2\text{.}\) We can think of \(M\) as specifying an injective function from \(V_1\) to \(V_2\text{.}\) If every vertex in \(V_2\) is also matched (i.e., \(V_2\) is covered), then the matching is called a perfect matching.

Finding a matching in a bipartite graph can be treated as a network flow problem.

In order for there to be a total matching from \(V_1\) to \(V_2\text{,}\) we need \(\deg(v_1)>0\) for each \(v_1\in V_1\text{.}\) However, that is not enough. Phillip Hall (1904–1982) discovered the following condition, known as Hall’s Marriage Theorem, needed for a total matching.

Hall actually stated and proved a more general theorem, but we have given its formulation in the context of graph theory.

A graph \(G=(V,E)\) is called \(k\)-regular if \(\deg(v)=k\) for every \(v\in V\text{.}\)