Spring 2014, Math 497/597, Topics in Graph Theory

Class: MW 3:00-4:15, MB 139

Instructor: Dr. Zach Teitler
Office: MG 233A
Phone: 208-426-1086
E-mail: zteitler@boisestate.edu
Office hours: TBA and by appointment

Syllabus: pdf, html

View course advertisement: pdf, html

Important dates:

Textbook: Graph Theory, by Bondy and Murty, Springer, 2008.
See the blog of the book for errata and hints to selected exercises.

Weekly schedule:
Dates Topics (planned) What we actually did
Week 1
Week 2
Week 3
Week 4
Week 5
Week 6
Week 7
Mar 3 Max-flow min-cut More proofs of Cayley's formula
Mar 5 Matchings: Berge's theorem, Hall's marriage theorem Flows and cuts
Week 8
Mar 10   Max-flow min-cut
Mar 12   Corollaries of max-flow min-cut
Week 9
Mar 17 Circulations, vector spaces associated to graphs  
Mar 19 Menger's theorem  
Week 10
Mar 31 Matchings, Hall's marriage theorem  
Apr 2    

Written Homework:
Homeworks 1-5 (show/hide)

Assigned date Assignment Suggested problems Due date
Wed, 1/22/14 1 § 1.1 #6, 11, 12, 14, 16, 17, 18, 20, 24
Wed, 1/29/14
Wed, 1/29/14 2 § 1.2 #8, 16, (20?); § 1.3 # 1, 2, 3
§ 2.1 #2, 7, 8, 13, 16-17, 20
§ 2.2 #3, 5, 6, 7, 11, 19, 21, 25
Wed, 2/5/14
Wed, 2/5/14 3 § 2.4 #3, 5, 7
§ 3.1 #5, 7, (11)
§ 3.2 #3, 4
§ 3.3 #1
Wed, 2/12/14
Short paper on open problem. Wed, 2/19/14
Wed, 2/19/14 4 § 3.3 #2, 8
§ 3.4 #9
§ 4.1 #7, 8, 9, 11, 12, 19
§ 4.2 #10, 14
By Exercise 1.1.6(a), every finite simple graph has at least one pair of vertices with the same degree. Characterize all finite simple graphs with exactly one such pair.
Wed, 2/26/14
Wed, 2/26/14 5 No suggested problems (sorry). Wed, 3/5/14
Wed, 3/5/14 6 No suggested problems (sorry). Wed, 3/12/14
Wed, 3/12/14 7 § 7.1 #3
§ 7.2 #4, 5, 6
§ 7.3 #3
  1. Suppose $F$ is a set of edges after whose deletion there is no flow from $s$ to $t$ with positive value. Prove that $F$ contains a cut separating $s$ from $t$.
  2. Let $G=(V,E)$ be a directed graph and let $c$ be an extended-real-valued capacity function on $E$. (Thus $c(xy)$ is a non-negative real or $+\infty$.) Let $s$ and $t$ be two vertices. Prove that either there is a flow from $s$ to $t$ with infinite value or else there is a flow with maximal finite value.
  3. By successively reducing the number of circular flows in $G$, prove that there is a maximal flow without circular flows in which no current enters the source and no current leaves the sink.
  4. Given a lower capacity $l(xy)$ and an upper capacity $c(xy)$ for each edge $xy$, with $0 \leq l(xy) \leq c(xy)$, we call a circulation $g$ feasible if $l(xy) \leq g(xy) \leq c(xy)$ for every edge $xy$. Prove that there exists a feasible circulation if and only if $l^+(S) \leq c^-(S)$ for every subset $S$ of vertices.
    (Here, $l^+(S)$ means the sum of lower capacities of edges leaving $S$, that is, the sum of $l^+(xy)$ for edges $xy$ with $x$ in $S$ and $y$ not in $S$; similarly, $c^-(S)$ means the sum of upper capacities of edges entering $S$.)
    [Hint available by email.]
Wed, 3/19/14
  1. § 12.3 #4. (In this problem, r_n=r_n(3,...,3), the least integer N such that any n-coloring of the edges of K_N has a monochromatic triangle.)
  2. § 12.3 #12 (theorem of Karolyi, Pach, Toth)
  3. By considering the 3-coloring of K_{16} with vertex set GF(16), the field of order 16, in which the color of an edge ij depends on the coset of the group of the cubic residues to which i-j belongs, show that R_3(3,3,3)=17. (You have to check that the graph is well defined.)
  4. (Easy.) Given 2 <= k <= n, denote by c_k(n) the maximal integer which is such that in every k-coloring of the edges of K_n we can find a connected monochromatic subgraph of order c_k(n). Show that c_2(n)=n.
  5. Let H_1 and H_2 be arbitrary graphs. Denote by r(H_1,H_2) the smallest integer n such that every red-blue coloring of the edges of K_n contains a red H_1 or a blue H_2.
    Show that r(C_4,C_4)=6.
  6. (Infinite Ramsey theory.) Let S be an infinite set of points in the plane. Show that there is an infinite subset A of S such that either A is contained in a line or no three points of A are collinear.
  7. (Infinite Ramsey theory.) Show that there is an infinite set of natural numbers such that the sum of any two elements has an even number of prime factors.
  8. (Infinite Ramsey theory.) (Difficult.) Show that there is a sequence n_1 < n_2 < ... of natural numbers such that if r <= i_1 < i_2 < ... < i_r then n_{i_1}+...+n_{i_r} has an even number of prime factors if and only if r has an odd number of prime factors.
  9. Define a graph with vertex set {1,...,n}^{(2)} (the collection of 2-element subsets of {1,2,...,n}) by joining a < b to b < c. Show that this graph does not contain a triangle and its chromatic number tends to infinity with N.
  10. (Infinite Ramsey theory.) Let g_1(x), g_2(x), ..., g_n(x) be bounded real functions and let f(x) be another real function. Let epsilon and delta be positive constants. Suppose max_i (g_i(x)-g_i(y)) > delta whenever f(x)-f(y) > epsilon. Prove that f is bounded.
Wed, 4/7/14

You may use this homework template (383 KB) if you wish. It is completely optional.


Back to main page