# 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.
Last changed by  
 
knikct
4460

Read more

JMM 2023 Special Session: Perspectives on Eigenvalue Computation

The official schedule is posted at https://www.jointmathematicsmeetings.org/meetings/national/jmm2023/2270_program_ss94.html#title The Zoom link for virtual attendance/virtual talks is: https://berkeley.zoom.us/j/94982941411?pwd=RWRXeVdoZUNVTmdqK1FIMksrZFllZz09 Friday, January 6 (101 Hynes Convention Center) 1-2pm: Matt Colbrook, The foundations of infinite-dimensional spectral computations (Zoom) 2-3pm: Josué Tonelli-Cueto, Condition-based Low-Degree Approximation of Real Polynomial Systems

1/3/2023
Math 55 Definition List

Lecture 1: Propositional Logic A proposition is a declarative sentence that is either true or false but not both. A proposition has a truth value which is either $T$ or $F$. A letter used to denote a proposition is called a propositional variable. If $p$ is a proposition, the negation of $p$, denoted $\lnot p$, is the proposition "it is not the case that $p$". The truth value of $\lnot p$ is the opposite of that of $p$. If $p$ and $q$ are propositions, the conjunction of $p$ and $q$ (denoted $p\land q$) is the proposition "p and q." Its truth value is $T$ when both $p$ and $q$ are $T$, and it is $F$ otherwise. If $p$ and $q$ are propositions,he disjunction of $p$ and $q$ is the proposition "p or q". Its truth value is $T$ when at least one of $p$ or $q$ is $T$, and $F$ if both $p$ and $q$ are $F$. If $p$ and $q$ are propositions, the conditional $p\rightarrow q$ is the proposition "if $p$ then $q$". Its truth values are given by the following truth table (which lists its truth values in terms of those of $p$ and $q$): [see Table 5 in Rosen] The converse of $p\rightarrow q$ is $q\rightarrow p$. A compound proposition consists of logical operations (the four listed above) applied to propositions or propositional variables, possibly with parentheses. The truth value of a compound proposition can be mechanically determined given the truth values of its constituents.

12/12/2022
Math 55 Graph Theory Practice Questions

Prove that every simple graph with $n$ vertices and $k$ edges has at least $n − k$ connected components (hint: induction, or contradiction). Let $p\ge 3$ be a prime. Consider the graph $G=(V,E)$ with $V={0,1,2,\ldots, (p-1)}$ and $$E={{x,y}:x-y\equiv 2(mod p)\lor x-y\equiv -2 (mod p)}$$ Show that $G$ is connected. Does $G$ have an Euler circuit? Prove your answer. Let $n\ge 1$ be an integer and let $k\le n/2$. Consider the graph $G=(V,E)$ with $V={S\subseteq {1,2,\ldots,n}: |S|=k}$ and $$E = {{S,T}:|(S-T)\cup (T-S)|=1}.$$ What are the degrees of the vertices in $G$? Is $G$ connected? For which values of $n$ and $k$ does $G$ have an Eulerian circuit? For which values of $n$ and $k$ is $G$ $2-$colorable? Prove your answers.

11/8/2022
Math 55 Graph Theory Practice Solutions

Prove that every simple graph with $n$ vertices and $k$ edges has at least $n − k$ connected components (hint: induction on $k$). Proof 1. We proceed by induction. Fix $n\ge 1$ and let $P(k)$ be the statement that every simple graph with $n$ vertices and $k$ edges has at least $n-k$ connected components. We will show that $P(k)$ is true for all $k\ge 0$. Basis Step: $P(0)$ says that a graph with no edges has at least $n$ connected components, and this is true since each vertex is its own connected component. Inductive Step: Assume $P(k)$ is true. Let $G$ be a graph with $n$ vertices and $k+1$ edges. Let $e=uv$ be an arbitrary edge of $G$, and let $G'=G-e$ be the graph obtained by deleting $e$. Let $G_1,\ldots,G_\ell$ be the connected components of $G'$ and note that $\ell \ge n-k$ by the inductive hypothesis. Notice that if $u$ and $v$ are in the same connected component of $G'$, then adding it does not change the connected components, so in this case $G$ also has $\ell$ connected components.

11/7/2022
Read more from knikct
Published on HackMD