# Math 55 Graph Theory Practice Solutions 1. 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. On the other hand if $u\in G_i$ and $v\in G_j$ for some $i\neq j$ then $G_i\cup G_j$ is a connected component of $G$, since there is a path from every $x\in G_i$ and $y\in G_j$ by concatenating a path from $x$ to $u$, the edge $uv$, and a path from $v$ to $y$. The other connected components of $G'$ remain connected components in $G$. Thus, the number of connected components decreases by at most one upon adding $e$, so the number of connected components in $G$ is at least $\ell-1 = n-k-1 = n-(k+1)$, as desired. *Proof 2.* By contradiction. Assume $G$ is a simple graph with $n$ vertices and $k$ edges. Assume $G$ has at most $n-k-1$ connected components. Let the connected components be $G_1,\ldots,G_m$, and suppose they have $n_1,n_2,\ldots,n_m$ vertices, where $n=n_1+n_2+\ldots+n_m$ Each connected component must contain a spanning tree, and these trees have $n_1-1,n_2-1,\ldots,n_m-1$ edges. Since these sets of edges are disjoint, the total number of edges in $G$ is at least $$(n_1-1)+(n_2-1)+\ldots (n_m-1) = (n_1+n_2+\ldots+n_m)-m $$ $$= n-m \ge n-(n-k-1) = k+1,$$ since $m\le n-k-1$, which is a contradiction. 2. 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. *Solution.* (i) Let $x,y$ be two vertices of $G$. Let $m=x-y$. We will show that there is an integer $k$ such that $m\equiv 2k (mod p)$, which will imply that $x,x+2,x+4,\ldots,x+2k=y$ is a path in $G$ between $x$ and $y$ if $k\ge 0$ and otherwise $x,x-2,x-4,\ldots,x+2k$ is a path in $G$ between $x$ and $y$ if $k<0$. To see that such a $k$ exists, observe that $2$ and $p$ are relatively prime since $p\ge 3$. Thus $2$ has an inverse modulo $p$, and any $k$ satisfying $k\equiv 2^{-1}m (mod p)$ is sufficient. (ii) Let $x\in V$. Observe that $xy$ is an edge if $x-y\equiv 2 (mod p)$ or $x-y\equiv -2(mod p)$. Each of these equations has a unique solution in $V$, so the degree of every vertex is $2$. By Euler's theorem, this means that $G$ has an Eulerian circuit. 3. 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. *Solution.* As stated, this question has a pretty boring answer: notice that for any subset $S\subseteq [n]$ of size $k$ and any other subset $T\neq S$, we must have $|(S-T)\cup (T-S)|\ge 2$ since $S$ must contain an element not in $T$ and $T$ must contain an element not in $S$ (as they are the same size). Thus, the edge set of this graph is empty, and the graph is simply the empty graph. The degrees are zero. The graph is not connected. The graph does not have an Eulerian circuit for any value of $k$. The graph is $2-$colorable for every value of $k$. 4. A much more interesting version of the previous question is to consider the graph with edges $$E = \{\{S,T\}:|(S-T)\cup (T-S)|=2\}.$$ *Solution.* In this case: the degrees are $k(n-k)$ since for any vertex $S$ there are $k$ choices of elements of $S$ to delete and $(n-k)$ choices of vertices outside $S$ to replace it with to obtain a neighbor $T$. The graph is connected if and only if $k\ge 2$, in which case we can construct a path between any distinct $S$ and $T$ by deleting one element of $S$ and adding one element of $T$ at a time. The graph has an Eulerian circuit iff the degree $k(n-k)$ is even and $k\ge 2$ (which is required for it to be connected). To determine whether the graph is $2-$colorable, we will determine whether it has an odd circuit. It turns out that if $n\ge 3$ then this graph always contains a triangle: if $k=1$ the vertices $\{1\},\{2\},\{3\}$ form a triangle, and if $k>1$ then by choosing any set $A$ satisfying $|A|=k-1$ and $A\cap\{1,2,3\}=\emptyset$ we obtain a triangle $\{1\}\cup A, \{2\}\cup A,\{3\}\cup A$ (such a set $A$ exists since $n\ge 2k\ge (k-1)+3$ when $k\ge 2$). Thus, when $n\ge 3$ the graph is not $2-$colorable since it contains an odd circuit. The only remaining possibility is that $n=2$, in which case $k=1$ and the graph consists of a single edge, which is $2-$colorable.
Last changed by  
 
knikct
492

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 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|$.

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
Read more from knikct
Published on HackMD