Summary of definitions and theorems in graph theory

Summary of definitions and theorems in graph theory

Introduction

1.1 Graphs and Graph Models

A Graph G consists of a finite nonempty set $V$ of objects called vertices and a set $E$ of 2-element subsets of $V$ called edges. The ses $V$ and $E$ are the vertex set and edge set of $G$, respectively. Write $G=(V,E)$.

Two graphs $G$ and $H$ are equal if $V(G)=V(H)$ and $E(G)=E(H)$, in which case we write $G=H$.

If $uv$ is an edge of $G$, then $u$ and $v$ are said to be adjacent in $G$.

The number of vertices in $G$ is often called the order of $G$, while the number of edges is its size.

A graph with exactly one vertex is called a trivial graph, implying that the order of a nontrivial graph is at least 2.

labeled graph and unlabeled graph

A graph $G$ is called a word graph if $G$ is the word graph of some set $S$ of 3-letter words.

1.2 Connected Graphs

The adjacent vertices $u$ and $v$ are said to be joined by the edge $e$. The vertices $u$ and $v$ are referred to as neighbors of each other.

Distinct edges incident with a common vertex are adjacent edges.

A graph $H$ is called a subgraph of a graph $G$, written $H \subseteq G$, if $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$. We also say that $G$ contains $H$ as a subgraph. If $H \subseteq G$ and either $V(H)$ is a proper subset of $V(G)$ or $E(H)$ is a proper subset of $E(G)$, then $H$ is a proper subgraph of $G$. If a subgraph of a graph $G$ has the same vertex set as $G$, then it is a spanning subgraph of $G$.

A subgraph $F$ of a graph $G$ is called an induced subgraph of $G$ if whenever $u$ and $v$ are vertices of $F$ and $uv$ is an edge of $G$, then $uv$ is an edge of $F$ as well.

If $S$ is a nonempty set of vertices of a graph $G$, then the subgraph of $G$ induced by $S$ is the induced subgraph with vertex set $S$. This induced subgraph is denoted by $G[S]$.

For a nonempty set $X$ of edges, the subgraph G[X] induced by $X$ has edge set $X$ and consists of all vertices that are incident with at least one edge in $X$. This subgraph is called an edge-induced subgraph of $G$.

A $u-v$ walk $W$ in $G$ is a sequence of vertices in $G$, beginning with $u$ and ending at $v$ such that consecutives vertices in the sequence are adjacent. If $u=v$, then the walk $W$ is closed; while if $u\not=v$, then $W$ is open. A walk of length 0 is a trivial walk.

We define a $u-v$ trial in a graph $G$ to be a $u-v$ walk in which no edges is traversed more than once.

A $u-v$ walk in a graph in which no vertices are repeated is a $u-v$ path.

A circuit in a graph $G$ is a closed trail of length 3 or more. Hence a circuit begins and ends at the same vertex but repeats no edges.

A circuit that repeats no vertex, except for the first and last, is a cycle.

If $G$ contains a $u-v$ path, then $u$ and $v$ are said to be connected and $u$ is connected to $v$.

A graph $G$ is connected if every two vertices of $G$ are connected. A graph that is not connected is called disconnected. A connected subgraph of $G$ that is not a proper subgraph of any other connected subgraph of $G$ is a component of $G$. The number of components of a graph $G$ is denoted by $k(G)$. Every graph is the union of its components.

The distance between $u$ and $v$ is the smallest length of any $u-v$ path in $G$ and is denoted by $d_{G}(u,v)$ or simply $d(u,v)$. A $u-v$ path of length $d(u,v)$ is called a $u-v$ **geodesic**.

The greatest distance between any two vertices of a connected graph $G$ is called the diameter of $G$ and is denoted by $diam(G)$.

Theorem 1.10 Let $G$ be a graph of order 3 or more. Then $G$ is connected if and only if $G$ contains two distinct vertices $u$ and $v$ such that $G-u$ and $G-v$ are connected.

1.3 Common Classes of Graphs

$G$ is called a path if …

$G$ is called a cycle if …

A graph $G$ is complete if every two distinct vertices of $G$ are adjacent. A complete graph of order $n$ is denoted by $K_n$.

The complement $\bar{G}$ of a graph $G$ is that graph whose vertex set is $V(G)$ and such that for each pair $u,v$ of distinct vertices of $G$, $uv$ is an edge of $\bar{G}$ if and only if $uv$ is not an edge of $G$.

The graph $\bar{K_n}$ has $n$ vertices and no edges, it is called the empty graph of order $n$.

Theorem 1.11 If $G$ is a disconnected graph, then $\bar{G}$ is connected.

Theorem 1.12 A nontrivial graph $G$ is a bipartite graph if and only if $G$ contains no odd cycles.

A graph $G$ is a bipartite graph if $V(G)$ can be partitioned into two subsets $U$ and $W$, called partite sets, such that every edge of $G$ joins a vertex of $U$ and a vertex of $W$.

If every vertex of $U$ is adjacent to every vertex of $W$ , then we call $G$ a complete bipartite graph . A complete graph with $|U|=s$ and $|W|=t$ is denoted by $K_{s,t}$ or $K_{t,s}$. If either $s=1$ or $t=1$, then $K_{s,t}$ is a **star**.

A graph $G$ is a $k$-partite graph if $V(G)$ can be partitioned into $k$ subsets $V_1$,$V_2$,…,$V_k$,(called partite sets) such that if $uv$ is an edge of $G$, then $u$ and $v$ belong to different partite sets. If, in addition, every two vertices in different partite sets are joined by an edge, then $G$ is a complete k-partite graph. If $|V_i|=n_i$ for $1 \le i \le k$, then we denote this graph by $K_{n1,n2,…,nk}$.

The join $G+H$ consists of $G \cup H$ and all edges joining a vertex of $G$ and a vertex of $H$.

The Cartesian product $G \times H$ has vertex set $V(G \times H) = V(G) \times V(H)$ . Two distinct vertices $(u,v$) and $(x,y)$ are adjacent in $G \times H$ if either (1) $u=x$ and $vy\in E(H)$ or (2) $v=y$ and $ux\in E(G)$.

We define $Q_1 $ to be $ K_2 $ and for $n \ge 2$, define $Q_{n}$ to be $Q_{n-1} \times K_2 $. The graphs $Q_n $ are then called $n$**-cubes** or **hypercubes**.

1.4 Multigraphs and Digraphs

A multigraph $M$ consists of a finite nonempty set $V$ of vertices and a set $E$ of edges, where every two vertices of M are joined by a finite number of edges(possibly zero). If two or more edges join the same pair of (distinct) vertices, then these edges are called parallel edges.

In a pseudograph, not only are parallel edges permitted but an edge is also permitted to join a vertex to itself. Such an edge is called a loop.

A digraph(or directed graph) $D$ is a finite nonempty set $V$ of objects called vertices together with a set $E$ of ordered pairs of distinct vertices. The elements of $E$ are called directed edges or arcs. If $(u,v)$ is a directed edge, then we indicate this in a diagram representing $D$ by drawing a directed line segment or curve from $u$ to $v$. Then u is said to be adjacent to v and v is adjacent from u.

If, in the definition of digraph, for each pair $u,v$ of distinct vertices, at most one of $(u,v)$ and $(v,u)$ is a directed edge, then the resulting digraph is an oriented graph

Degrees

2.1 The Degree of a Vertex

The degree of a vertex $v$ in a graph $G$ is the number of edges incident with $v$ and is denoted by $deg_G \ v$ or simply by $deg \ v$ if the graph $G$ is clear from the context. The set $N(v)$ of neighbors of a vertex $v$ is called the neighborhood of $v$. Thus $deg \ v = |N(v)|$.

A vertex of degree 0 is referred to as an isolated vertex and a vertex of degree 1 is an end-vertex(or a leaf).

The minimum degree of $G$ is the minimum degree among the vertices of $G$ and is denoted by $\delta(G)$, the maximum degree of $G$ is denoted by $\Delta(G)$.

For $G$ of order $n$, we have $0 \le \delta(G) \le deg \ v \le \Delta(G) \le n-1$.

Theorem 2.1(The First Theorem of Graph Theory) If $G$ is a graph of size $m$, then $\sum \limits_{v\in V(G)} deg \ v =2m$.

A vertex of even degree is called an even vertex, while a vertex of odd degree is an odd vertex.

Corollary 2.3 Every graph has an even number of odd vertices.

If a graph $G$ order $n$ contains a vertex of degree $n-1$, then $G$ is connected. However, this is not a necessary condition.

Theorem 2.4 Let $G$ be a graph of order $n$. If $deg \ u + deg \ v \ge n-1$, for every two nonadjacent vertices $u$ and $v$ of $G$ , then $G$ is connected and $diam(G) \le 2$.

Corollary 2.5 If $G$ is a graph of order $n$ with $\delta(G) \ge (n-1)/2$, then $G$ is connected.

outdegree and indegree.

2.2 Regular Graphs

If $\delta(G)=\Delta(G)$, then the vertices of $G$ have the same degree and $G$ is called regular. If $deg \ r=r$ for every vertex $v$ of $G$, where $0 \le r \le n-1$, then $G$ is $r$ -regular or regular of degree r.

A 3-regular graph is also referred to as a cubic graph. The best known cubic graph may very well be the Petersen graph.

Theorem 2.6 Let $r$ and $n$ be integers with $0 \le r \le n-1$. There exists an r-regular graph of order $n$ if and only if at least one of $r$ and $n$ is even.

Theorem 2.7 For every graph $G$ and every integer $r \ge \Delta(G)$, there exists an r-regular graph $H$ containing $G$ as an induced subgraph.

2.3 Degree Sequences

If the degrees of the vertices of a graph $G$ are listed in a sequence $s$, then $s$ is called a degree sequence of $G$.

A finite sequence of nonnegative integers is called graphical if it is a degree sequence of some graph.

Theorem 2.10 A non-increasing sequence $s$: $d_1 ,d_2 ,…,d_n (n\ge 2)$ of non-negative integers, where $d_1 \ge 1$, is graphical if and only if the sequence $s_1：d_2 -1,d_ 3-1,…,d_{d_ 1 + 1}-1,d_{d_ 1+1}-1,d_{d_ 1+2},…d_ n $ is graphical.

Isomorphic Graphs

3.1 The Definition of Isomorphism

We call two graphs $G$ and $H$ “isomorphic” if they have the same structure and write $G \cong H$ to indicate this.

Formally, two (labeled) graphs $G$ and $H$ are isomorphic (have the same structure) if there exists a one-to-one correspondence $\phi$ from $V(G)$ to $V(H)$ such that $uv \in E(G)$ if and only if $\phi(u)\phi(v) \in E(H)$. In this case, $\phi$ is called an isomorphism from $G$ to $H$.

Theorem 3.1 Two graphs $G$ and $H$ are isomorphic if and only if their complements $\bar{G}$ and $\bar{H}$ are isomorphic.

A graph $G$ is self-complementary if $G\cong \bar{G}$ .

Theorem 3.2 If $G$ and $H$ are isomorphic graphs, then the degrees of the vertices of $G$ are the same as the degrees of the vertices of $H$.

Note: Having the same degree sequences don’t necessarily mean two graph are isomorphic.

Trees

4.1 Bridges

An edge $e=uv$ of a connected graph $G$ is called a bridge of $G$ if $G-e$ is disconnected.

An edge $e$ is a bridge of a disconnected graph if $e$ is a bridge of some component of $G$.

An edge $e$ is a bridge of a graph $G$ if and only if $k(G-e)=k(G)+1$

End-vertice: vertice with degree $1$.

Theorem 4.1: An edge $e$ of a graph $G$ is a bridge if and only if $e$ lies on no cycle of $G$

4.2 Trees

A graph G is called acyclic if it has no cycles.

A tree is an acyclic connected graph.

Every edge in a tree is a bridge.

A tree containing exactly two vertices that are not end-vertices(which are necessarily adjacent) is called a double star.

A caterpillar is a tree of order 3 or more, the removal of whose end-vertices produces a path called spine of the caterpillar.

Choose a vertex of a tree $T$, and designate this vertex as the root of $T$. The tree $T$ then becomes a rooted tree.

Acyclic graphs are also referred to as forests. Therefore each component of a forest is a tree.

The one fact that distinguishes trees from forests is that a tree is required to be connected, while a forest is not required to be connected.

Theorem 4.2 A graph $G$ is a tree if and only if every two vertices of G are connected by a unique path.

Theorem 4.3 Every nontrivial tree has at least two end-vertices.

Theorem 4.4 Every tree of order n has size $n-1$

Corollary 4.6 Every forest of order n with k components has size $n-k$

Theorem 4.7 The size of every connected graph of order $n$ is at least $n-1$.

Theorem 4.8 Let $G$ be a graph of order $n$ and size $m$. If $G$ satisfies any two of the properties: (1) $G$ is connected, (2)$G$ is acyclic, (3)$m=n-1$, then $G$ is a tree.

Theorem 4.9 Let $T$ be a tree of order $k$. If $G$ is a graph with $\delta(G) \ge k-1$, then $T$ is isomorphic to some subgraph of $G$

4.3 The Minimum Spanning Tree Problem

A spanning subgraph $H$ of a connected graph $G$ such that $H$ is a tree is called a spanning tree of $G$.

Theorem 4.10 Every connected graph contains a spanning tree.

The weight $w(H)$ of $H$ is defined as the sum of the weights of its edges.

A spanning tree with the minimum weight is called a minimum spanning tree.

The problem of finding a minimum spanning tree in a connected weighted graph is called the Minimum Spanning Tree Problem.

Kruskal’s Algorithm: For a connected weighted graph $G$, a spanning tree $T$ of $G$ is constructed as follows: For the first edge $e_1$ of $T$, we select any edge of $G$ of minimum weight and for the second edge $e_2$ of $T$, we select any remaining edge of $G$ of minimum weight. For the thrid edge $e_3$ of T, we choose any remaining edge of $G$ of minimum weight that does not produce a cycle with the previously selected edges. We continue in the manner until a spanning tree is produced.

Theorem 4.11 Kruskal’s Algorithm produces a minimum spanning tree in a connected weighted graph.

Prim’s Algorithm: For a connected weighted graph $G$, a spanning tree $T$ of $G$ is constructed as follows: For an arbitrary vertex $u$ for $G$, an edge of minimum weight incident with $u$ is selected as the first edge $e_1$ of $T$. For subsequent edges $e_2$, $e_3$, ..,$e_{n-1}$, we select an edge of minimum weight among those edges having exactly one of its vertices incident with an edge already selected.

Theorem 4.12 Prim’s Algorithm produces a minimum spanning tree in a connected weighted graph.

4.4 Excursion: The Number of Spanning Trees

THeorem 4.15 The number of distinct trees of order n with a specified vertex set is $n^{n-2}$.

Matrix Tree Theorem (to be continued).

Connectivity

5.1 Cut-Vertices

A vertex $v$ in a connected graph $G$ is a cut-vertex of $G$ if $G-v$ is disconnected. More generally, a vertex $v$ is a cut-vertex in a graph $G$ if $v$ is a cut-vertex of a component of $G$.

Theorem 5.1 Let $v$ be a vertex incident with a bridge in a connected graph $G$. Then $v$ is a cut-vertex of $G$ if and only if $deg \ v \ge 2$.

Corollary 5.2 Let $G$ be a connected graph of order 3 or more. If $G$ contains a bridge, then $G$ contains a cut-vertex.

Theorem 5.3 Let $v$ be a cut-vertex in a connected graph $G$ and let $u$ and $w$ be vertices in distinct components of $G-v$ . Then $v$ lies on every $u-w$ path in $G$.

Corollary 5.4 A vertex $v$ of a connected graph $G$ is a cut-vertex of $G$ 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 5.5 Let $G$ be a nontrivial connected graph and let $u\in V(G)$ . If $v$ is a vertex that is farthest from $u$ in $G$, then $v$ is not a cut-vertex of $G$.

Corollary 5.6 Every nontrivial connected graph contains at least two vertices that are not cut-vertices.

5.2 Blocks

A nontrivial connected graph with no cut-vertices is called a nonseparable graph.

Theorem 5.7 A graph of order at least 3 is nonseparable if and only if every two vertices lie on a common cycle.

Theorem 5.8 Let $R$ be the relation defined on the edge set of a nontrivial connected graph $G$ by $e \ R \ f$, where $e,f \in E(G)$, if $e=f$ or $e$ and $f$ lie on a common cycle of $G$. Then $R$ is an equivalence relation.

Corollary 5.9 Every two distinct blocks $B_1$ and $B_2$ in a nontrivial connected graph $G$ have the following properties:

5.3 Connectivity

By a vertex-cut in a graph $G$, we mean a set $U$ of vertices of $G$ such that $G-U$ is disconnected. A vertex-cut of minimum cardinality in $G$ is called a minimum vertex-cut.

Note: A connected graph contains a vertex-cut if and only if $G$ is not complete.

For a graph $G$ that is not complete, the vertex-connectivity(or simply the connectivity) $\kappa(G)$ of $G$ is defined as the cardinality of a minimum vertex-cut of $G$; if $G=K_n$ for some positive integer $n$, then $\kappa(G)$ is defined to be $n-1$. $$0 \le \kappa(G) \le n-1$$.

For a nonnegative integer $k$, a graph $G$ is said to be $k$-connected if $\kappa(G) \ge k$.

An edge-cut in a nontrivial graph $G$ is a set $X$ of edges of $G$ such that $G-X$ is disconnected.

An edge-cut $X$ of a connected graph $G$ is minimal if no proper subset of $X$ is an edge-cut of $G$. If $X$ is a minimal edge-cut of a connected graph $G$, then $G-X$ contains exactly two components $G_1$ and $G_2$. Necessarily then , $X$ consists of all those edges of $G$ joining $G_1$ and $G_2$.

An edge-cut of minimum cardinality is called a minimum edge-cut.

The edge-connectivity …….

For a nonnegative integer $k$, …

Theorem 5.11 For every graph $G$, $$ \kappa(G) \le \lambda(G) \le \delta(G) $$

Theorem 5.12 If $G$ is a cubic graph, then $\kappa(G) = \lambda(G)$.

Theorem 5.13 If $G$ is a graph of order $n$ and size $m \le n-1$, then $\kappa(G) \le \lfloor \frac{2m}{n} \rfloor$ .

$\kappa(T)=1$

Let $G$ be a connected graph of diameter $d$. For an integer $k$ with $1 \le k \le d$, the $k$th power $G^k $ of $G$ is the graph with $V(G^k ) = V(G)$ such that $uv$ is an edge of $G^k$ if $1 \le d_{G} (u,v) \le k$.

Theorem 5.14 If $G$ is a connected graph of order at least 3, then its square $G^2$ is 2-connected.

Theorem 5.15 For every two integers $r$ and $n$ with $2 \le r \le n$, $$\kappa(H_{r,n})=r$$.

5.4 Menger’s Theorem

TBC.

Traversability

6.1 Eulerian Graphs

A circuit $C$ in a graph $G$ is called an Eulerian circuit if $C$ contains every edge of $G$. Since no edges is repeated in a circuit, every edge appears exactly once in an Eulerian circuit. A connected graph that contains an Eulerian circuit is called an Eulerian graph.

For a connected graph $G$, we refer to an open trial that contains every edge of $G$ as an Eulerian trial.

Theorem 6.1 A nontrivial connected graph $G$ is Eulerian if and only if every vertex of $G$ has even degree.

Theorem 6.2 A connected graph $G$ contains an Eulerian trial if and only if exactly two vertices of $G$ have odd degree. Furthermore, each Eulerian trial of $G$ begins at one of these odd vertices and ends at the other.

We have a conclusion: Let $G$ and $H$ be nontrivial connected graphs. Then $G \times H$ is Eulerian if and only if both $G$ and $H$ are Eulerian or every vertex of $G$ and $H$ is odd.

6.2 Hamiltonian Graphs

A cycle in a graph $G$ that contains every vertex of $G$ is called a Hamiltonian cycle of $G$. A Hamiltonian graph is a graph that contains a Hamiltonian cycle.

A path in a graph $G$ that contains every vertex of $G$ is called a Hamiltonian path in $G$.

Theorem 6.4 The Petersen graph is non-Hamiltonian.

Theorem 6.5 If $G$ is a Hamiltonian graph, then for every nonempty proper set $S$ of vertices of $G$, $$\kappa(G-S) \le |S|$$

Theorem 6.6 Let $G$ be a graph of order $n \ge 3$. If $deg \ u + deg \ v \ge n$ for each pair $u$, $v$ of nonadjacent vertices of $G$, then $G$ is Hamiltonian.

Corollary 6.7 Let $G$ be graph of order $n \ge 3$. If $deg \ v \ge n/2$ for each vertex $v$ of $G$, then $G$ is Hamiltonian.

Theorem 6.8 Let $u$ and $v$ be nonadjacent vertices in a graph $G$ of order $n$ such that $deg \ u + deg \ v \ge n$ . Then $G+uv$ is Hamiltonian if and only if $G$ is Hamiltonian.

The closure $C(G)$ of a graph $G$ of order $n$ is the graph obtained from $G$ by recursively joining pairs of nonadjacent vertices whose degree sum is at least $n$ (in the resulting graph at each stage) until no such pair remains.

Theorem 6.9 A graph is Hamiltonian if and only if its closure is Hamiltonian.

Corollary 6.10 If $G$ is a graph of order at least 3 such that $C(G)$ is complete, the n $G$ is Hamiltonian.

Theorem 6.11 Let $G$ be a graph of order $n \ge 3$. If for every integer $j$ with $ 1 \le j < \frac{n}{2}$, the number of vertices of $G$ with degree at most $j$ is less than $j$, then $G$ is Hamiltonian.

6.3 Hamiltonian Walks

Matchings and Factorization

8.1 Matchings

A set of edges in a graph is independent if no two edges in the set are adjacent.

By a macthing in a graph $G$ , we mean an independent set of edges in $G$.

The graph $G$ is said to satisfy Hall’s condition if $|N(X)| \ge|X|$ for every nonempty subset $X$ of $U$.

Theorem 8.3 Let $G$ be a bipartite graph with partite sets $U$ and $W$ such that $r= |U| \le |W|$. Then $G$ contains a matching of cardinality $r$ if and only if $G$ satisfies Hall’s condition.

Theorem 8.4 A collection ${ S_1 , S_2 , … , S_n}$ of nonempty finite sets has a system of distinct representatives if and only if for each integer $k$ with $1 \le k \le n$, the union of any $k$ of these sets contains at elast $k$ elements.

Theorem 8.5(The Marriage Theorem) In a collection of $r$ women and $r$ men, a total of $r$ marriages between acquainted couples is possible if and only if for each integer $k$ with $1 \le k \le r$, every subset of $k$ women is collectively acquainted with at least $k$ men.

A matching of maximum cardinality is called a maximum matching.

If a graph $G$ of order $2k$ has a matching $M$ of cardinality $k$, then this (necessarily maximum) matching $M$ is called a perfect matching as $M$ matches every vertex of $G$ to some vertex of $G$ .

Theorem 8.6 Every r-regular bipartite graph($r \ge 1$) has a perfect matching.

The edge independence number $\alpha'(G)$ of a graph $G$ is the maximum cardinality of an independent set of edges.

Furthermore, a graph $G$ of order $n$ has a perfect matching if and only if $n$ is even and $\alpha ‘(G) = n/2$.

A vertex and an incident edge are said to cover each other.

An edge cover of a graph $G$ without isolated vertices is a set of edges of $G$ that covers all vertices of $G$.

The edge covering number $\beta’(G)$ of a graph $G$ is the minimum cardlinality of an edge cover of $G$. An edge cover of $G$ of cardinality $\beta'(G)$ is a minimum edge cover of $G$.

Theorem 8.7 For every graph $G$ of order $n$ containing no isolated vertices, $$\alpha(G')+ \beta(G')=n$$.

A set of vertices in a graph is independent if no two vertices in the set are adjacent. The vertex independence number (or the independence number) $\alpha(G)$ of a graph $G$ is the maximum cardinality of an independent set of vertices in $G$. An independent set in $G$ of cardinality $\alpha(G)$ is called a maximum independent set.

A vertex cover in a graph $G$ is a set of vertices that covers all edges of $G$. The minimum number of vertices in a vertex cover of $G$ is the vertex covering number $\beta(G)$ of $G$. A vertex cover of cardinality $\beta(G)$ is a minimum vertex cover in $G$.

Theorem 8.8 For every graph $G$ of order $n$ containing no isolated vertices, $$\alpha(G) + \beta(G) =n$$.

8.2 Factorization

A 1-regular spanning subgraph of a graph $G$ is also called a 1-factor of $G$.

A graph $G$ has a 1-factor if and only if $G$ has a perfect matching.

A component of a graph is odd or even according to whether its order is odd or even. We write $k_O (G)$ for the number of odd components of a graph $G$.

Theorem 8.10 A graph $G$ contains a 1-factor if and only if $k_O (G-S) \le |S|$ for every proper subset $S$ of $V(G)$.

Theorem 8.11(Petersen’s Theorem) Every 3-regular bridgeless graph contains a 1-factor.

Theorem 8.12 Every 3-regular graph with at most two bridges contains a 1-factor.

A graph $G$ is said to be 1-factorable if there exists 1-factors $F_1,F_2,…,F_r$ of $G$ such that ${E(F_1),E(F_2),..,E(F_r)}$ is a partition of $E(G)$. We then say that $G$ is factored into the 1-factors $F_1.F_2,…,F_r$ , which form a 1-factorization of $G$.

Every 1-factorable graph is regular.

Theorem 8.13 The Petersen graph is not 1-factorable.

Theorem 8.14 For each positive integer $k$, the complete graph $K_{2k}$ is 1-factorable.

Theorem 8.15 Every r-regular bipartite graph , $r\ge 1$, is factorable.

A 2-factor in a graph $G$ is a spanning 2-regular subgraph of $G$. Every component of a 2-factor is therefore a cycle. A graph $G$ is said to be 2-factorable if there exist 2-factors $F_1,F_2,..,F_k$ such that ${E(F_1),E(F_2),…,E(F_k)}$ is a partition of $E(G)$.

Theorem 8.16 A graph $G$ is 2-factorable if and only if $G$ is r-regular for some positive even integer $r$.

A spanning subgraph $F$ of a graph $G$ is called a factor of $G$. The graph $G$ is said to be factorable into the factors $F_1,F_2,…,F_k$ if ${E(F_1),E(F_2),…,E(F_k)}$ is a partition of $E(G)$. If each factor $F_i$ is isomorphic to some graph $G$, then $G$ is F-factorable.

TBC.

8.3 Decompositions and Graceful Labelings

A graph $G$ is said to be decomposable into the subgraphs $H_1,H_2,…,H_k$ if ${E(H_1),E(H_2),…,E(H_k)}$ is a partition of $E(G)$. Such a partition produces a decomposition of $G$. If each $H_i$ is isomorphic to some graph $H$, then the graph $G$ is $H-$ decomposable and the decomposition is an $H-$ decomposition.

A Steiner triple system of order $n$ is a set $S$ of cardinality $n$ and a collection $T$ of 3-element subsets, called triples, such that every two distinct elements of $S$ belong to a unique triple in $T$.

TBC

Planarity

9.1 Planar Graphs

A graph $G$ is called a planar graph if $G$ can be drawn in the plane so that no two of its edges cross each other. A graph that is not planar is called nonplanar. A graph $G$ is called a plane graph if it is drawn in the plane so that no two edges of $G$ cross.

A plane graph divides the plane into connected pieces called regions. In every plane graph, there is always one region that is unbounded. This is the exterior region. The subgraph of a plane graph whose vertices and edges are incident with a given region $R$ is the boundary of $R$.

Theorem 9.1(The Euler Identity) If $G$ is a connected plane graph of order $n$, size $m$ and having $r$ regions, then $n-m+r=2$.

Theorem 9.2 If $G$ is a planar graph of order $n \ge 3$ and size $m$, then $$m \le 3n-6$$.

Corollary 9.3 Every planar graph contains a vertex of degree 5 or less.

Corollary 9.4 The complete graph $K_5$ is nonplanar.

Theorem 9.5 The graph $K_{3,3}$ is nonplanar.

A graph $G$ is maximal planar if $G$ is planar but the addition of an edge between any two nonadjacent vertices of $G$ results in a nonplanar graph.

More formally, a graph is called a subdivision of a graph $G$ if $G'=G$ or one or more vertices of degree 2 are inserted into one or more edges of $G$.

Theorem 9.7(Kuratowski’s Theorem) A graph $G$ is planar if and only if $G$ does not contain a subdivision of $K_5$ or $K_{3,3}$ as a subgraph.

Coloring Graphs

10.2 Vertex Coloring

With each map, there is associated a graph $G$ called the dual of the map, whose vertices are the regions of the map and such that two vertices of $G$ are adjacent if the corresponding regions are neighboring regions.

By a proper coloring (or, more simply, a coloring) of a graph $G$ , we mean an assignment of colors (elements of some set) to the vertices of $G$ , one color to each vertex, such that adjacent vertices are colored differently.

The smallest number of colors in any coloring of a graph $G$ is called the chromatic number of $G$ and is denoted by $\chi(G)$. If it is possible to color $G$ from a set of $k$ colors, then $G$ is said to be k-colorable. A coloring that uses $k$ colors is called a k-coloring. If $\chi(G)=k$, then $G$ is said to be k-chromatic and every $k-coloring$ of $G$ is a minimum coloring of $G$.

Theorem 10.1(The Four Color Theorem) The chromatic number of every planargraph is at most 4.

If $G$ is a k-chromatic graph, then it is possible to partition $V(G)$ into $k-1$ independent sets $V_1 , V_2 , …., V_k $, called color classes, but it is not possible to partition $V(G)$ into $k-1$ independent sets.

Theorem 10.2 A graph $G$ has chromantic number 2 if and only if $G$ is a nonempty bipartite graph.

A graph $G$ of order $n$ has chromatic number $n$ if and only if $G =K_n$.

If $H$ is a subgraph of $G$, then $\chi(H) \le \chi(G)$.

A clique in a graph $G$ is a complete subgraph of $G$. The order of the largest clique ina graph $G$ is its clique number, which is denoted by $\omega(G)$.

In fact, $\alpha(G)=k$ if and only if $\omega(\bar{G})=k$.

Theorem 10.5 For every graph $G$ of order $n$, $\chi(G \ge \omega(G))$ and $\chi(G) \ge \frac{n}{\alpha(G)}$.

Theorem 10.7 For every graph $G$, $$\chi(G) \le 1 + \Delta(G)$$

Theorem 10.8(Brooks' Theorem) For every connected graph $G$ that is not an odd cycle or a complete graph, $\chi(G) \le \Delta(G)$.

Theorem 10.9 For every graph $G$, $\chi(G) \le 1+ max{\delta(H)}$, where the maximum is taken over all induced subgraphs $H$ of $G$.

The shadow graph $S(G)$ of a graph $G$ is obtained from $G$ by adding, for each vertex $v$ of $G$, a new vertex $v'$, called the shadow vertex of $v$ , and joining $v'$ to the neighbors of $v$ in $G$. Observe that (1) a vertex of $G$ and its shadow vertex are not adjacent in $S(G)$ and (2) no two shadow vertices are adjacent in $S(G)$.

Theorem 10.10 For every integer $k \ge 3$, there exists a triangle-free graph with chromatic number $k$.

A graph $G$ is called perfect if $\chi(H)=\omega(H)$ for every induced subgraph $H$ of $G$.

The Perfect Graph Theorem A graph is perfect if and only if its complement is perfect.

The Strong Perfect Graph T A graph $G$ is perfect if and only if neither $G$ nor $\bar{G}$ contains an induced odd cycle of length 5 or more.

Reference:

[1] G.Chartrand and P.Zhang, First Course in Graph Theory, New York: Dover Publications, 2012.