# 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).$\square$ ### 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, \ldots, x_{k-1},e_k,x_k$$ where $e_i=\{x_{i-1},x_i\}\in E$ for all $i=1\ldots k$. The path is said to *connect* $x_0,x_k$, *visit* the vertices $x_0,\ldots,x_k$, and *traverse* the edges $e_1,\ldots,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,\ldots,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\rightarrow \{1,\ldots, k\}$ such that $f(x)\neq 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,\ldots,x_{k-1},e_k,x_k$of length$k$where$k$is odd. Assume for contradiction that$f:V\rightarrow\{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\neq x$of$G$, choose a path$\pi_y$from$x$to$y$(which is possible since$G$is connected). Define a function$f:V\rightarrow\{red,blue\}$as follows: let$f(x)=red$and$f(y)=blue$whenever$length(\pi_y) is odd$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$\Pi_a,ab,$and the reversal of$\Pi_b$. Notice that$length(C)=length(\Pi_a)+length(\Pi_b)+1$and since$G$has no odd circuit,$length(C)\equiv 0 (mod 2)$. This means that$length(\Pi_a)+length(\Pi_b)\equiv 1 (mod 2)$, so in particular they cannot be both odd or both even. Thus,$f$is a valid$2-$coloring, as desired.$\square$*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\rightarrow \{1,\ldots, k\}$such that$f(x)\neq 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'=(V',E')$where$V'=V - \{x\}$and$E'=\{e\in E: e$is not incident with$x\}$, i.e.,$G'$is the graph obtained by deleting$x$and all edges incident with it from$G$. Notice that$G'$has at most$k$vertices and maximum degree at most$D$, so by the inductive hypothesis there exists a$D+1$-coloring$f':V'\rightarrow \{1,\ldots,D+1\}$of$G'$. Let$x_1,\ldots,x_m$be the neighbors of$x$in$G$. Let$j$be any color in$\{1\ldots,D+1\}-\{f'(x_1),\ldots,f'(x_m)\}$--- note that such a color exists since$m\le D$. Define a coloring$f:V\rightarrow \{1,\ldots,D+1\}$by extending$f'$as follows: $$f(y)=f'(y) \quad y\neq 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'$has endpoints of distinct colors because$f'$is a valid$D+1$-coloring of$G'$. Thus,$G$is$D+1$-colorable, as desired.$\square$### 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,\ldots,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,\ldots,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'$is a subgraph of$G$such that$H\neq H'$and$H$is a subgraph of$H'$, then$H'$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,\ldots, 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 $$\overline{G}=(V,\{ \{u,v\} : \{u,v\}\textrm{ 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$\overline{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,\ldots,x_{i-1}$. This process terminates at some path$x_0,\ldots,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},\ldots,x_k,x_i$would be a cycle contained in$T$, so$T$must contain a leaf.$\square$**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'=T-x$. Notice that$T'$is still connected since every pair of vertices in$T'$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'$has$k-1$edges. Since$x$was a leaf,$T$has$k$edges, as desired.$\square$**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.* ($\rightarrow$) 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'$in$G'$obtained by replacing every occurrence of$e$by$C-e$. By induction$G'$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.$\square$### HW9.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'-\{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,\ldots,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$.$\square$*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,\ldots,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,\ldots 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,\ldots, k$contains each edge of$C\cup H_1\cup\ldots H_k$exactly once. So$C$is an Eulerian circuit of$G$, as desired.$\square$### HW9.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.