Bena Tshishiku

Bena Tshishiku

Mathematician

Graph theory (Math 1030)

Undergraduate course, Brown University, 2026

Announcements

  • (2/6). HW3 is posted below and is due next Friday 2/13.
  • (2/4). Office hours for the semester are Wed 5-6 in Kassar 304 and Thurs 4-5 in Kassar 104 (common room)
  • (2/1). Some solutions to HW1 are posted below. For this I’ve selected some good solutions among those submitted by you all, among which there were many to choose from.

Course information

This is an undergraduate course in the study of graphs. Graphs appear all over the place: both in pure and applied mathematics as well as other sciences, such as chemistry, physics, computer science, and linguistics. We will focus on the theoretical aspects of graph theory, although we will also discuss some applications.

Course objectives

  • learn about basic properties of graphs (bipartite, Eulerian, matchings, connectivity, colorability, planarity,…)
  • prove foundational results (Menger, Hall matching, matrix tree,…);
  • understand theoretical trends in graph theory (local-to-global, duality, extremal problems, Ramsey theory);
  • investigate connections of graph theory to different areas (combinatorics, topology, linear algebra, probability);
  • improve your ability to read/write proofs and critique arguments;
  • expose you to things you haven’t seen and challenge you through problem solving.

Some experience with writing proofs will help.

Textbook

West, Introduction to graph theory

Course expenses

Just the textbook. In practice, the text may not be absolutely necessary for the course, although you may want it as a reference.

Grading

homework 30%, midterm 20%, final project 20%, final exam 20%, participation 10%

  • a grade of 92% or higher is guaranteed an A
  • a grade of 84% or higher is guaranteed an B
  • a grade of 76% or higher is guaranteed an C

For students taking this course S/NC, a minimum grade of 70% and a minimum participation grade of 70% is necessary to receive a grade of S.

Contact information

  • (Instructor) Bena Tshishiku: bena_tshishiku at brown.edu
  • TAs: Rafi Ash (rafael_ash at brown.edu)

Course events

Lectures: MWF 9-9:50 in Kassar 205

Office hours:

  • Bena: Wednesdays 5-6 in Kassar 304
  • Rafi: Thursdays 4-5 in Kassar 104 (common room)

Important dates:

  • Midterm: March 10 in the evening (tentative, time TBD)
  • Final projects: presented in class during reading period
  • Final exam: Thursday, May 7 at 2pm

Homework

There will be weekly assignments posted below. The homework is designed to increase your engagement with the material, with your peers, and with me.

Collaboration is encouraged. Working with your classmates can help you learn the material better. Some of the homework problems may be difficult, so it is recommended that you talk to someone when you are stuck. That said, you are required to write your solutions alone and acknowledge the students you worked with. For any solution you submit, you should understand it well enough that you can explain it to someone else and answer questions about it. If you find yourself writing down things that you can’t explain, you should go back and think more about the problem.

LaTeX: Homework solutions must be typed in LaTeX. If you’re new to LaTeX, you can either download LaTex or use sharelatex which allows you download, edit, and compile LaTeX files online. See here for some commonly used symbols in LaTeX. Also Detexify is a useful tool for finding the commands for various symbols. The source code for the assignments should be a helpful guide. The most basic thing to know/remember is that math always goes in between dollar signs.

Late homework policy: As a general rule, late homework is not accepted. I know things happen, so I will drop your lowest assignment. For exceptional circumstances, please email me.

Homework assignments.

HW1 (due 1/30). TeX file, image (put this in the same folder as your tex file), student solutions

HW2 (due 2/6). TeX file

HW2 (due 2/13). TeX file

Participation

Occasionally, we may have assignments or quizzes in class. These will count toward the participation part of your grade (10%).

You can also participate by coming to office hours and asking questions on Ed Discussion.

Final Project

Working in groups of 2, you’ll choose a topic related to the course to investigate and create an N-minute presentation to be given during reading period. To help you prepare for this, I will ask you to submit the following.

  • Final project proposal (due 3/31)
  • Final project outline (due 4/7)
  • Final project slides (due 4/14)

Additional information, as well as some potential topic ideas, will be shared later.

Tentative schedule (subject to change)

  • Week 1: Introduction (West pg 1-11, 13, 34-36, 38);
    • Wed (1/21). Graphs, vertex degrees, degree-sum formula, isomorphism
    • Fri (1/23). degree sequences, subgraphs, Gray codes
  • Week 2: Fundamental concepts (West 19-30, 44-46);
    • Mon (1/26). no class (snow day)
    • Wed (1/28). degree sequences, bipartite graphs
    • Fri (1/30). bipartite graphs, local-to-global results, Eulerian graphs; HW1 due
  • Week 3: Trees (West 68-71, 73-75, 81-83)
    • Mon (2/2). characterization of trees, spanning trees,
    • Wed (2/4). counting trees, Bridg-it
    • Fri (2/6). Cayley’s theorem, minimal spanning trees; HW2 due
  • Week 4: Matchings (West 107-115)
    • Mon (2/9). matchings, Hall’s theorem, vertex covers, maximum matchings, Konig’s theorem
    • Wed (2/11).
    • Fri (2/13). HW3 due
  • Week 5: Matchings (West 130-132)
    • Mon (2/16). No class (university holiday)
    • Wed (2/18). Konig’s theorem, stable matchings, Gale-Shapely
    • Fri (2/20). HW4 due
  • Week 6: Connectivity (West 149-150, 167-168, 176-181, 183)
    • Mon (2/23). vertex cut, Menger’s theorem, flows on networks, matrix-tree theorem, Ford-Fulkerson
    • Wed (2/25).
    • Fri (2/27). HW5 due
  • Week 7: Coloring (West 191-194, 204-208)
    • Mon (3/2). Chromatic number, greedy coloring, Brooks’ theorem, Mycielski construction, extremal problem, Turan graphs, chromatic polynomial
    • Wed (3/4).
    • Fri (3/6). HW6 due
  • Week 8: Planarity (West 6.1-6.2)
    • Mon (3/9). chromatic polynomial, planar graphs, Kuratowski’s theorem, linear planar embeddings
    • Tue (3/10). Midterm (time TBD)
    • Wed (3/11).
    • Fri (3/13).
  • Week 9: Planarity
    • Mon (3/16). Art gallery problem, map coloring, platonic solids
    • Wed (3/18).
    • Fri (3/20). HW7 due

  • Week 10: Spring Break

  • Week 11: Ramsey theory (West 8.3)
    • Mon (3/30). Ramsey theory for graphs, numbers, and knots
    • Tue (3/31). Final project proposal due
    • Wed (4/1).
    • Fri (4/3). HW8 due
  • Week 12: Ramsey theory, Random graphs (West 8.5)
    • Mon (4/6). Ramsey lower bound, random graphs, connectedness and diameter of random graphs, Rado graph
    • Tue (4/7). Final project outline due
    • Wed (4/8).
    • Fri (4/10). HW9 due
  • Week 13: Random graphs, Spectral graph theory (West 8.6)
    • Mon (4/13).
    • Tue (4/14). Final project slides due
    • Wed (4/15).
    • Fri (4/17). HW10 due
  • Week 14:
    • Mon (4/20).
    • Wed (4/22).
    • Fri (4/24). start of reading period
  • Week 15:
    • Mon (4/27). final projects
    • Wed (4/29). final projects
    • Fri (5/1). final projects
  • Week 16:
    • Thurs. Final exam 2-5pm

Tips for success

  • Attend lecture.
  • Read the book. Doing this before lecture may help you absorb the lectures better.
  • Try the homework problems alone before working with others or coming to office hours. Identifying where you get stuck can make office hours more productive.
  • Don’t use AI for the homework. The point of HW is to challenge you to think in new ways. AI is counterproductive for this purpose. If you are stuck come to office hours or find someone to work with to make progress. You will learn more that way.
  • Come to office hours. There are many good uses of office hours: ask questions related to homework, lecture, or the book; go over something you’re confused about; work on your homework alone or in a group; ask for advice on how to improve in the course; ask about something only tangentially related to the course.
  • Use the homework to better understand the material. A pretty good general approach to doing homework problems is to follow UMER: (1) Understand the problem: review all relevant definitions, do some examples, draw a picture; (2) Make a plan: come up with strategies to solve the problem, which results from class are relevant; (3) Execute: try one of your strategies, and if it doesn’t work (this is normal), try another, go back to steps (1) and (2) as necessary; (4) Reflect on your solution: after you’ve solved the problem (great) there is more to do(!), check your work, did you miss any steps, can you simplify or improve your solution, are there any big-picture take-aways. Each step of UMER should reinforce your understanding of the course material. Overall, the homework should be fun if you have a good sense of UMER.