Math 55 Fall 2022 Graph Theory Notes

Lecture 14

Basic Terminology, Handshaking Theorem

A graph is a pair

$G=(V,E)$ where

$V$ is a finite set of vertices and

$E$ is a finite multiset of

$2-$element subsets of

$V$, called edges. If

$E$ has repeated elements

$G$ is called a multigraph, otherwise it is called a simple graph. We will not consider directed graphs or graphs with loops (edges from a vertex to itself).

Two vertices

$x,y\in V$ are adjacent if

$\{x,y\}\in E$. An edge

$e=\{x,y\}$ is said to be incident with

$x$ and

$y$. The degree of a vertex

$x$ is the number of edges incident with it.

Theorem. In any graph

$G=(V,E)$,

$$\sum _{v\in V}deg(v)=2|E|.$$
Proof. Let

\(I=\{(e,v):e\in E,v\in V,\textrm{\)e$ is incident with

$v$ in

$G$}}$ be the set of edge-vertex incidences in

$G$. We will count the number of incidences in two ways:
(i) Observe that every edge participates in exactly two incidences, and no incidence participates in more than one edge. Thus, the total number of incidences is

$|I|=2|E|$.
(ii) Observe that each vertex

$v$ participates in exactly

$deg(v)$ incidences, and no incidence participates in more than one vertex. Thus the total number of incidences is

$|I|=\sum _{v\in V}deg(v)$.
The theorem follows from (i) and (ii).

$◻$

2-coloring and odd circuits

A path of length

$k$ in

$G$ is an alternating sequence of vertices and edges

$$x_0,e_1,x_1,e_2,\dots ,x_{k-1},e_k,x_k$$
where

$e_i=\{x_{i-1},x_i\}\in E$ for all

$i=1\dots k$. The path is said to connect

$x_0,x_k$, visit the vertices

$x_0,\dots ,x_k$, and traverse the edges

$e_1,\dots ,e_k$. A path is called simple if it contains no repeated vertices. If

$x_0=x_k$ then the path is called a circuit. Note that in a simple graph (i.e., a graph with no multiple edges), a path is uniquely specified by the sequence of vertices

$x_0,\dots ,x_k$ (as there is only one possible choice of edge between each pair of consecutive vertices). A graph

$G$ is connected if for every pair of distinct vertices

$x,y$ of

$G$, there is a path in

$G$ between

$x$ and

$y$.

A k-coloring of

$G$ is a function

$f:V\to \{1,\dots ,k\}$ such that

$f(x)\ne f(y)$ whenever

$x$ is adjacent to

$y$. A graph is

$k-$colorable if it has a

$k$-coloring. (in class we did the case

$k=2$)

Theorem. Let

$G=(V,E)$ be a connected graph. Then

$G$ is $2-colorable if and only if

$G$ does not contain a circuit of odd length.

Proof. (->) We show the contrapositive. Assume

$G$ has a circuit

$C=x_0,e_1,x_1,\dots ,x_{k-1},e_k,x_k$ of length

$k$ where

$k$ is odd. Assume for contradiction that

$f:V\to \{red,blue\}$ is a

$2-$coloring of

$G$. Assume without loss of generality that

$f(x_0)=red$, and observe by the definition of

$2-$coloring that

$f(x_1)=blue,f(x_2)=red$, etc., with

$f(x_i)=red$ if

$i$ is even and

$f(x_i)=blue$ if

$i$ is odd. In particular,

$f(x_{k-1})=red$ since

$k$ is odd. But this violates the definition of

$k-$coloring since

$e_k=\{x_{k-1},x_0\}$ is an edge of

$G$.

(<-) Assume

$G$ is connected and contains no odd circuit. Let

$x$ be an arbitrary vertex of

$G$. For every vertex

$y\ne x$ of

$G$, choose a path

${\pi }_y$ from

$x$ to

$y$ (which is possible since

$G$ is connected). Define a function

$f:V\to \{red,blue\}$ as follows: let

$f(x)=red$ and

$f(y)=blue$ whenever

$length({\pi }_y)isodd$ and

$f(y)=red$ whenever

$length({\pi }_y)$ is even.

We will show that

$f$ is a valid

$2-$coloring of

$G$. Let

$ab\in E$ be an arbitrary edge. Consider the circuit

$C$ formed by concatenating

${\mathrm{\Pi }}_a,ab,$ and the reversal of

${\mathrm{\Pi }}_b$. Notice that

$length(C)=length({\mathrm{\Pi }}_a)+length({\mathrm{\Pi }}_b)+1$ and since

$G$ has no odd circuit,

$length(C)\equiv 0(mod2)$. This means that

$length({\mathrm{\Pi }}_a)+length({\mathrm{\Pi }}_b)\equiv 1(mod2)$, so in particular they cannot be both odd or both even. Thus,

$f$ is a valid

$2-$coloring, as desired.

$◻$

The proof of the second direction above is different from the proof in class in two ways. (i) I chose an arbitrary path to each

$y$ in order to define the coloring and not the shortest path. This is perfectly valid if you are ok with making an arbitrary choice, and a bit less in line with our intuition of coloring the neighbors of

$x$ followed by their neighbors, etc. (ii) I showed

$f$ is a coloring via a direct proof rather than by contradiction. It is intructive to read both the proof above and the proof from Lecture 15.

HW8.1 Problems

1. Let
   $n$ be a positive integer. Prove that the hypercube graph on
   $n$ bits (as defined in class) is connected.
2. Suppose
   $G$ is a connected graph. Show that between every pair of distinct vertices of
   $G$, there is a simple path connecting
   $x$ to
   $y$ in
   $G$.
3. The degree sequence of a graph is a list of the degrees of its vertices in nonincreasing order. Prove that if a simple graph has degree sequence 2, 2, 2, 1, 1, 1, 1 then it must
   be disconnected.

Lecture 15

A graph

$H=(W,F)$ is a subgraph of

$G$ if

$W\subseteq V$ and

$F\subseteq E$. If

$W=V$ then

$H$ is called a spanning subgraph of

$G$.

Two common ways to construct subgraphs of a given graph

$G=(V,E)$:

1. Delete a vertex and all of its incident edges.
2. Delete an edge, leaving the vertices the same.

A k-coloring of

$G$ is a function

$f:V\to \{1,\dots ,k\}$ such that

$f(x)\ne f(y)$ whenever

$x$ is adjacent to

$y$.

Chromatic Number is at most

$D+1$

Theorem. If a graph

$G=(V,E)$ has maximum degree

$D$, then

$G$ is

$D+1$-colorable.

Proof. Let

$D\ge 1$. We proceed by induction. Let

$P(n)$ be the statement "every graph with

$n$ vertices and maximum degree at most

$D$ can be

$D+1$-colored".

Base case:

$P(1)$ says that the graph with a single isolated vertex can be

$D+1$-colored, which is true.

Inductive Step: Let

$k\ge 1$ and assume

$P(k)$. Let

$G=(V,E)$ be a graph on

$k+1$ vertices. Choose an arbitrary vertex

$x\in V$. Let

$G^{\prime }=(V^{\prime },E^{\prime })$ where

$V^{\prime }=V-\{x\}$ and

$E^{\prime }=\{e\in E:e$ is not incident with

$x\}$, i.e.,

$G^{\prime }$ is the graph obtained by deleting

$x$ and all edges incident with it from

$G$. Notice that

$G^{\prime }$ has at most

$k$ vertices and maximum degree at most

$D$, so by the inductive hypothesis there exists a

$D+1$-coloring

$f^{\prime }:V^{\prime }\to \{1,\dots ,D+1\}$ of

$G^{\prime }$.

Let

$x_1,\dots ,x_m$ be the neighbors of

$x$ in

$G$. Let

$j$ be any color in

$\{1\dots ,D+1\}-\{f^{\prime }(x_1),\dots ,f^{\prime }(x_m)\}$ –- note that such a color exists since

$m\le D$. Define a coloring

$f:V\to \{1,\dots ,D+1\}$ by extending

$f^{\prime }$ as follows:

$$f(y)=f^{\prime }(y)y\ne x$$

$$f(x)=j$$
Observe that

$f$ is a valid

$D+1$-coloring of

$G$ since every edge incident to

$x$ has endpoints of distinct colors by the choice of

$j$, and every edge in

$G^{\prime }$ has endpoints of distinct colors because

$f^{\prime }$ is a valid

$D+1$-coloring of

$G^{\prime }$. Thus,

$G$ is

$D+1$-colorable, as desired.

$◻$

HW 8.2

Defn. If

$G=(V,E)$ is a graph, a subset

$S\subseteq V$ is called a clique if

$xy\in E$ for every pair of distinct vertices

$x,y\in S$.

$S$ is called an independent set if

$xy\notin E$ for every pair of distinct vertices

$x,y\in S$.

1. Prove that if
   $G=(\{1,\dots ,6\},E)$ is a graph then it contains either
   $3$ vertices which form a clique or
   $3$ vertices which form an independent set. (hint: see lecture 15 part III)
2. Prove that if
   $G=(V,E)$ is
   $k-$colorable then there are disjoint sets
   $V_1,\dots ,V_k\subseteq V$ (i.e.,
   $V_i\cap V_j=\varnothing$ for every
   $i,j\le k$) with
   $\bigcup _{i=1}^k{V}_i=V$ such that each
   $V_i$ is an independent set.

Defn. If

$G=(V,E)$ is a graph, a subgraph

$H$ of

$G$ is called a connected component of

$G$ if

$H$ is connected and maximal, i.e., it is not possible to add any vertices or edges to

$H$ while keeping it connected (formally: if

$H^{\prime }$ is a subgraph of

$G$ such that

$H\ne H^{\prime }$ and

$H$ is a subgraph of

$H^{\prime }$, then

$H^{\prime }$ must be disconnected.). Read page 717 of Rosen for additional intuition about connected components.

3. Prove that every nonempty graph contains at least one connected component. (hint: choose an arbitrary vertex and put it in
   $H$. If
   $H$ is a maximal subgraph we are done, otherwise choose a vertex to add to
   $H$,etc.)
4. Prove that every graph
   $G=(V,E)$ is a disjoint union of its connected components, i.e., there are subgraphs
   $G_1,\dots ,G_k$ for some
   $k$ with disjoint sets of vertices
   $V_i$ such that each
   $G_i$ is a connected component of
   $G$ and
   ${\cup }_{i=1}^k{V}_i=V$. (hint: induction)
5. The complement of a simple graph
   $G=(V,E)$ is the graph

$$\bar{G}=(V,\{\{u,v\}:\{u,v\}\text{ is not an element of }E\}),$$

i.e., the graph whose edges are the non-edges of G. Show that for every graph G, if G is not connected then its complement

$\bar{G}$ must be connected. (hint: consider the connected components of

$G$)

Lecture 16

A connected component of

$G$ is a maximal connected subgraph of

$G$, i.e. a subgraph

$H\subseteq G$ such that

$H$ is connected and adding any vertices to

$H$ would make it disconnected.

A cycle is a simple circuit circuit with no repeated edges and no repeated vertices, except the endpoints. A graph is called acyclic if it does not contain a cycle as a subgraph. (Note that under this definition, the graph consisting of a single edge is acyclic, but any graph which is not simple contains a cycle. Moreover, a cycle in a simple graph must have at lesat three vertices.)

A connected acyclic graph is called a tree. Note that a graph which is not simple cannot be a tree, since any multiedge constitutes a cycle.

Properties of Trees

A leaf is a vertex of degree one.

Theorem. Every tree with at least two vertices has at least one leaf.

Proof. Let

$x_0$ be a vertex in

$T$. Let

$x_1$ be any vertex in

$T$ adjacent to

$x_0$. Inductively construct a simple path by choosing

$x_{i+1}$ to be a vertex adjacent to

$x_i$ distinct from

$x_0,\dots ,x_{i-1}$. This process terminates at some path

$x_0,\dots ,x_k$ when it is not possible to extend the path any further, either because

$x_k$ isa leaf or because

$x_k$ is adjacent only to previously visited vertices

$x_i$ for

$i<k$. The latter case is impossible since then

$x_i,x_{i+1},\dots ,x_k,x_i$ would be a cycle contained in

$T$, so

$T$ must contain a leaf.

$◻$

Theorem. Every tree on

$n$ vertices has exactly

$n-1$ edges.

Proof. We proceed by induction on the number of vertices of the tree. When

$n=1$ the claim is true. Let

$T$ be a tree on

$k+1$ vertices. By the above theorem,

$T$ has at least one leaf vertex

$x$. Let

$T^{\prime }=T-x$. Notice that

$T^{\prime }$ is still connected since every pair of vertices in

$T^{\prime }$ is connected by a path which does not visit

$x$ (since

$x$ is a leaf, no simple path between two other vertices visits

$x$). Thus,

$T^{\prime }$ has

$k-1$ edges. Since

$x$ was a leaf,

$T$ has

$k$ edges, as desired.

$◻$

Theorem. Every tree is

$2$-colorable.
Proof. By induction. See the lecture slides.

Every Connected Graph Contains a Spanning Tree

Theorem. A graph is connected if and only if it contains a spanning tree.

Proof. (

$\to$) By induction. If

$G$ contains a cycle

$C$, let

$e$ be any edge in

$C$. Notice that

$G-e$ is connected since if

$x,y$ were connected by a path

$\pi$ in

$G$, then they are connected by a path

${\pi }^{\prime }$ in

$G^{\prime }$ obtained by replacing every occurrence of

$e$ by

$C-e$. By induction

$G^{\prime }$ contains a spanning tree, so

$G$ contains a spanning tree, as desired.

(

$\leftarrow$) Suppose

$G$ contains a spanning tree

$T$. Let

$x$ and

$y$ be arbitrary vertices in

$G$. Since

$T$ is spanning, these are also vertices in

$T$, and since

$T$ is connected there is a path

$\pi$ in

$T$ between

$x$ and

$y$. Since

$T$ is a subgraph of

$G$,

$\pi$ is also a path in

$G$, so

$G$ is connected, as desired.

$◻$

HW8.1

1. Show that a graph
   $G=(V,E)$ is a tree if and only if for every pair of distinct vertices
   $x,y\in V$, there is a unique path between
   $x$ and
   $y$ in
   $G$.
2. Show that if a tree contains a vertex of degree
   $k$, then it must have at least
   $k$ leaves.
3. Show that if
   $T=(V,E)$ is a tree and
   $e\in E$ then the spanning subgraph
   $T^{\prime }-\{e\}$ of
   $T$ is disconnected.
4. Suppose
   $G$ is a graph with
   $n$ vertices and
   $n-1$ edges. Show that
   $G$ is connected if and only if
   $G$ is acyclic.

Lecture 17

Definition. An Eulerian circuit of a connected multigraph

$G$ is a circuit which traverses every edge of

$G$ exactly once.

Euler's theorem

Theorem 1. If

$G$ is a connected multigraph with at least two vertices which has an Eulerian circuit, then the degree of every vertex in

$G$ must be even.
Proof. See lecture slides.

Theorem 2. If

$G$ is a connected multigraph with at least two vertices and the degree of every vertex in

$G$ is even, then

$G$ has an Eulerian circuit.

Lemma. If every vertex in a multigraph

$G$ has degree at least

$2$, then

$G$ contains a cycle.
Proof. We show the contrapositive. Assume

$G$ is acyclic and let

$G$ be the union of its connected components

$G_1,\dots ,G_k$. Each component is connected and acyclic, so each

$G_i$ must be a tree. If some

$G_i$ has at least two vertices, then it must have a leaf (by a theorem from the previous lecture), so

$G$ has a vertex of degree

$1$. Otherwise, each

$G_i$ is an isolated vertex, so every vertex of

$G$ has degree

$0$.

$◻$

Proof of Theorem 2. We proceed by induction on the number of edges. The minimum number of edges is

$2$, and the only graph with the property is two vertices joined by two edges, for which the claim is true.

Assume the theorem holds for all graphs with up to

$n$ edges. Let

$G$ be a connected multigraph with

$n+1$ edges and every degree even. By the Lemma,

$G$ contains a cycle

$C$. If

$G=C$ we are done. Otherwise, consider the graph

$H=G-E(C)$, and let

$H_1,\dots ,H_k$ be its connected components which have at least two vertices.

Observe that degree of every vertex in

$H_i$ is even, for every

$i=1,\dots k$ since the degree of each vertex in

$C$ is even, which means we deleted an even number of edges from each vertex.

Claim: in each

$H_i$ there exists a (not necessarily unique) vertex

$s_i\in H_i$ such that

$s_i\in C$.

By the induction hypothesis, each

$H_i$ has an Eulerian circuit

$C_i$ beginning and ending at

$s_i$. Now observe that the circuit obtained by replacing the first occurrence of

$s_i$ in

$C$ by

$C_i$, for

$i=1,\dots ,k$ contains each edge of

$C\cup H_1\cup \dots H_k$ exactly once. So

$C$ is an Eulerian circuit of

$G$, as desired.

$◻$

HW8.2

1. Prove that if
   $H$ is a connected component of
   $G$ and
   $v$ is a vertex in
   $H$, then the degree of
   $v$ in
   $H$ is equal to the degree of
   $v$ in
   $G$.
2. Prove the Claim in the proof of Theorem 2 above (which is the same as the claim from Lecture 17).
3. Prove that if a simple graph contains a circuit with no repeated edges, then it must contain a circuit with no repeated vertices (i.e., a simple circuit).
4. Prove or disprove: There exists a connected graph with
   $6$ vertices and
   $5$ edges which has an Euler circuit.
5. Prove or disprove: there exists a connected graph with
   $6$ vertices and
   $7$ edges which has an Euler circuit.

Extra Practice Problems