Computing and Data Science

Graph Theory

Sign in to Overleaf and use this template to write your solutions.

  1. Choose a public transit line. Define and draw a graph to represent that line.
  2. Given the following connections on a social media platform:
    Alice is friends with Ben and Cara
    Ben is friends with Alice, Dana, and Evan
    Cara is friends with Alice, Fiona, and George
    Dana is friends with Ben and Henry
    Evan is friends with Ben and Isla
    Fiona is friends with Cara and George
    George is friends with Cara, Fiona, and Henry
    Henry is friends with Dana, George, and Julia
    Isla is friends with Evan and Julia
    Julia is friends with Henry and Isla
    1. Draw a network (graph) of the relationships.
    2. How many connections away is Alice from Julia?
    3. What is the minimum number of connections that can be removed so there is no way to connection from Alice to Julia?
  3. A group of five people (Alejandro, Ben, Camille, Dalia, and Elias) all want to join three clubs (Xylophone, Yodeling, and Zoology).
    1. Define and draw the complete bipartite graph representing club memberships. How many memberships result?
    2. How many memberships would result for \(n\) people joining \(m\) clubs?
  4. Fred, along with the five people from the previous problem need to split into two groups of three for a project. However, there is drama! Alejandro refuses to work with Camille or Elias; Dalia "just can't even" with Ben or Camille; Ben and Camille both had a falling out with Fred; "aint no way" Elias will work with Dalia.
    1. Define and draw a graph \(W\), with six vertices, to represent who CANNOT work with whom.
    2. Show that it is possible to create two groups of three by partitioning \(W\) into a bipartite graph with three vertices on each side.
    3. Find \(\bar{W}\), the complement of \(W\). What does \(\bar{W}\) represent?

  5. Consider a standard four-way intersection with stop lights pointing in all four directions.

    There are twelve total lights that can be On (\(1\)) or Off (\(0\)), and we can represent the current state of those lights with a \(12\)-bit binary word: \[R_1Y_1G_1R_2Y_2G_2R_3Y_3G_3R_4Y_4G_4\] For example, with green lights both On in one direction while the other direction has red lights, we can write: \[001100001100\] which means that \(G_1\) and \(G_3\) are On while \(R_2\) and \(R_4\) are on.

    Create a directed graph to represent the behavior of the stop lights as they transition from one state to the next.

  6. Draw all of the (non-isomorphic) trees with \(|V|=6\).
  7. The three graphs below correspond to three famous polyhedra.
    v1v2v3v4
    12345678
    acbedf
    For each graph,
    1. Redraw the graph as a planar graph (with no edges crossing).
    2. Show that the graph either does or does not contain an Eulerian trail.
    3. Show that the graph either does or does not have a Hamiltonian path.
  8. Find the minimum spanning tree of:
  9. The graph \(H\) below represents towns and the the distance in km between neighboring towns.
    AberdaleBelmontClaremontDuxbury4257
    1. Write the weighted adjacency matrix for \(H\).
    2. There is some minimum distance between every pair of towns (not just adjacent towns). What is the average minimum distance?
    3. Write a matrix where each element is the minimum distance between each pair of towns.
  10. In terms of \(n\) and \(m\), how many vertices and edges does each graph below have? In other words, find an expression for \(|V|\) and \(|E|\) for each graph type. Suggestion: start with small examples and make a table.

    1. \(K_{n}\)
    2. \(K_{n,m}\)
    3. \(C_{n}\)
    4. \(P_{n}\)
  11. Exercises from Levin 4.1.
  12. Exercises from Levin 4.5.