Skip to main content

Chapter 10 Graphs

Exercises Practice Problems

1. Our First Graph.

A graph is a set \(V\) of vertices and a set \(E\) of edges connecting pairs of points. By convention, we denote the number of vertices by \(n=|V|\) and the number of edges by \(m = |E|\text{.}\)

Here is an example. The vertices are points and the edges are lines connecting pairs of points.

This graph \(G\) has \(|V|=6\) and \(|E|=8\text{.}\)

  • \((u,v)\) is an edge that is incident with both \(u\) and \(v\text{.}\) Therefore, \(u\) and \(v\) are adjacent.

  • \((x,w)\) is not an edge

  • \(w\) is incident with 3 edges, so its degree is \(\deg(w)=3\text{.}\)

  1. What are the degrees of the vertices of \(G\text{?}\)

  2. The graph \(G\) is drawn so that some of the edges are crossing, meaning that they intersect. For example, edge \(e_1 = (x,v)\) crosses edge \(e_2 = (y,w)\text{.}\) Create another drawing of the graph \(G\) so that none of the edges are crossing.

  3. The complement \(\overline{G}\) of graph \(G\) is the "graph of edges missing in \(G\text{.}\)" It has the same vertices as \(G\text{.}\) But the edge \((u,v) \in E(\overline{G})\) if and only if \((u,v) \notin E(G)\text{.}\) Draw the complement \(\overline{G}\) of the graph \(G\text{.}\) Can you draw \(\overline{G}\) so that none of its edges are crossing?

2. Families of Graphs.

  1. Paths. The path \(P_n\) is the graph consisting of a path on \(n\) vertices.

    How many edges are there in \(P_n\) for \(n \geq 2\text{?}\)

  2. Cycles. The cycle \(C_n\) is the graph corresponding to a closed walk on \(n\) vertices whose only repetition is the first/last vertex.

    How many edges are there is the cycle \(C_n\) for \(n \geq 3\text{?}\)

  3. Wheels. The wheel \(W_n\) is the graph consisting of a cycle \(C_{n-1}\) along with a single hub node that is adjacent with each node in that cycle.

    How many edges are there in the wheel \(W_n\) for \(n \geq 4\text{?}\)

  4. Complete Graphs. The complete graph \(K_n\) is the graph on \(n\) vertices with every possible edge.

    How many edges are there in the complete graph \(K_n\) for \(n \geq 2\text{?}\)

  5. Complete Bipartite Graphs. The complete bipartite graph \(K_{r,s}\) is the graph whose vertices are divided into sets \(A\) and \(B\text{,}\) where \(|A|=r\) and \(|B|=s\text{.}\) Every vertex in \(A\) is adjacent to every vertex in \(B\text{.}\) There are no other edges.

    How many edges are there in the complete bipartite graph \(K_{r,s}\) for \(r \geq 1\) and \(s \geq 1\text{?}\)

3. Counting edges and degrees.

Let \(G = (V,E)\) be a graph on \(n\) vertices with \(m\) edges.

  1. The Handshaking Lemma. Prove that

    \begin{equation*} \sum_{v \in V} \deg(v) = 2|E|. \end{equation*}

    This is our first example of a "combinatorial identity": you are counting the same set in two different ways. This equality is known as "the handshaking lemma."

  2. Prove that the number of vertices of odd degree is even. First, partition \(V\) into two sets: the vertices of odd degree and the vertices of even degree. Then use the handshaking lemma (from the previous problem).

  3. Prove that if \(G\) is a connected graph on \(n\) vertices then \(G\) contains two vertices that have the same degree. Hint: what are the possible values for \(\deg(v)\) for \(v \in V(G)\text{?}\)

4. Connected Graphs.

A graph is connected when every pair of vertices are connected by a path in the graph. Any graph is made up of connected components. In other words, we can view any graph as the union of its components, which are themselves connected graphs. Below, we see an example of a connected graph and example of a graph with three components.

  1. Let \(G\) be a graph with \(|V|=n\text{.}\)

    1. Suppose \(G\) is connected. Find a lower bound on \(|E|\text{.}\) Start by exploring examples for \(n=2,3,4,5\text{.}\) You do NOT have to prove your answer is correct.

    2. Suppose that \(G\) is disconnected. Find an upper bound on \(|E|\text{.}\) Start by exploring examples for \(n=2,3,4,5\text{.}\) You do NOT have to prove your answer is correct.

5. Bipartite Graphs.

A graph \(G=(V,E)\) is bipartite if its vertex set can be partitioned into two sets \(A\) and \(B\) such that the only edges in \(G\) run between these two sets. Equivalently: we can color the vertices of a bipartite graph with two colors, red and black, so that adjacent vertices receive different colors. The complete bipartite graph \(K_{n,m}\) is an example of a bipartite graph. Here are some more examples of bipartite graphs.

  1. For which values of \(n\) is \(P_{n}\) a bipartite graph?

  2. For which values of \(n\) is \(C_{n}\) a bipartite graph?

  3. For which values of \(n\) is \(W_{n}\) a bipartite graph?

  4. For which values of \(n\) is \(K_{n}\) a bipartite graph?

  5. Suppose that \(G\) is a bipartite graph on \(n\) vertices. Find an upper bound on \(|E|\text{.}\) Start by exploring examples for \(n=2,3,4,5\text{.}\) You do not need to prove your answer is correct.