# 4.S: Graph Theory (Summary)

- Page ID
- 14770

\( \def\d{\displaystyle}\)

\( \newcommand{\f}[1]{\mathfrak #1}\)

\( \newcommand{\s}[1]{\mathscr #1}\)

\( \def\N{\mathbb N}\)

\( \def\B{\mathbf{B}}\)

\( \def\circleA{(-.5,0) circle (1)}\)

\( \def\Z{\mathbb Z}\)

\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)

\( \def\Q{\mathbb Q}\)

\( \def\circleB{(.5,0) circle (1)}\)

\( \def\R{\mathbb R}\)

\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)

\( \def\C{\mathbb C}\)

\( \def\circleC{(0,-1) circle (1)}\)

\( \def\F{\mathbb F}\)

\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)

\( \def\A{\mathbb A}\)

\( \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\)

\( \def\X{\mathbb X}\)

\( \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\)

\( \def\E{\mathbb E}\)

\( \def\O{\mathbb O}\)

\( \def\U{\mathcal U}\)

\( \def\pow{\mathcal P}\)

\( \def\inv{^{-1}}\)

\( \def\nrml{\triangleleft}\)

\( \def\st{:}\)

\( \def\~{\widetilde}\)

\( \def\rem{\mathcal R}\)

\( \def\sigalg{$\sigma$-algebra }\)

\( \def\Gal{\mbox{Gal}}\)

\( \def\iff{\leftrightarrow}\)

\( \def\Iff{\Leftrightarrow}\)

\( \def\land{\wedge}\)

\( \def\And{\bigwedge}\)

\( \def\entry{\entry}\)

\( \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\)

\( \def\Vee{\bigvee}\)

\( \def\VVee{\d\Vee\mkern-18mu\Vee}\)

\( \def\imp{\rightarrow}\)

\( \def\Imp{\Rightarrow}\)

\( \def\Fi{\Leftarrow}\)

\( \def\var{\mbox{var}}\)

\( \def\Th{\mbox{Th}}\)

\( \def\entry{\entry}\)

\( \def\sat{\mbox{Sat}}\)

\( \def\con{\mbox{Con}}\)

\( \def\iffmodels{\bmodels\models}\)

\( \def\dbland{\bigwedge \!\!\bigwedge}\)

\( \def\dom{\mbox{dom}}\)

\( \def\rng{\mbox{range}}\)

\( \def\isom{\cong}\)

\(\DeclareMathOperator{\wgt}{wgt}\)

\( \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}\)

\( \newcommand{\va}[1]{\vtx{above}{#1}}\)

\( \newcommand{\vb}[1]{\vtx{below}{#1}}\)

\( \newcommand{\vr}[1]{\vtx{right}{#1}}\)

\( \newcommand{\vl}[1]{\vtx{left}{#1}}\)

\( \renewcommand{\v}{\vtx{above}{}}\)

\( \def\circleA{(-.5,0) circle (1)}\)

\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)

\( \def\circleB{(.5,0) circle (1)}\)

\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)

\( \def\circleC{(0,-1) circle (1)}\)

\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)

\( \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\)

\( \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\)

\( \def\ansfilename{practice-answers}\)

\( \def\shadowprops

Callstack: at (Template:MathJaxLevin), /content/body/div/p[1]/span, line 1, column 11 at template() at (Bookshelves/Combinatorics_and_Discrete_Mathematics/Book:_Discrete_Mathematics_(Levin)/4:_Graph_Theory/4.S:_Graph_Theory_(Summary)), /content/body/p[1]/span, line 1, column 22

\( \renewcommand{\bar}{\overline}\)

\( \newcommand{\card}[1]{\left| #1 \right|}\)

\( \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)

\( \newcommand{\lt}{<}\)

\( \newcommand{\gt}{>}\)

\( \newcommand{\amp}{&}\)

\( \newcommand{\hexbox}[3]{

\def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}

\def\y{-\r*#1-sin{30}*\r*#1}

\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

\draw (\x,\y) node{#3};

}\)

\(\renewcommand{\bar}{\overline}\)

\(\newcommand{\card}[1]{\left| #1 \right|}\)

\(\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)

\(\newcommand{\lt}{<}\)

\(\newcommand{\gt}{>;}\)

\(\newcommand{\amp}{&}\)

Hopefully this chapter has given you some sense for the wide variety of graph theory topics as well as why these studies are interesting. There are many more interesting areas to consider and the list is increasing all the time; graph theory is an active area of mathematical research.

One reason graph theory is such a rich area of study is that it deals with such a fundamental concept: any pair of objects can either be related or not related. What the objects are and what “related” means varies on context, and this leads to many applications of graph theory to science and other areas of math. The objects can be countries, and two countries can be related if they share a border. The objects could be land masses which are related if there is a bridge between them. The objects could be websites which are related if there is a link from one to the other. Or we can be completely abstract: the objects are vertices which are related if their is an edge between them.

What question we ask about the graph depends on the application, but often leads to deeper, general and abstract questions worth studying in their own right. Here is a short summary of the types of questions we have considered:

- Can the graph be drawn in the plane without edges crossing? If so, how many regions does this drawing divide the plane into?
- Is it possible to color the vertices of the graph so that related vertices have different colors using a small number of colors? How many colors are needed?
- Is it possible to trace over every edge of a graph exactly once without lifting up your pencil? What other sorts of “paths” might a graph posses?
- Can you find subgraphs with certain properties? For example, when does a (bipartite) graph contain a subgraph in which all vertices are only related to one other vertex?

Not surprisingly, these questions are often related to each other. For example, the chromatic number of a graph cannot be greater than 4 when the graph is planar. Whether the graph has an Euler path depends on how many vertices each vertex is adjacent to (and whether those numbers are always even or not). Even the existence of matchings in bipartite graphs can be proved using paths.

## Chapter Review

### 1

Which (if any) of the graphs below are the same? Which are different? Explain.

**Solution**-
The first and the third graphs are the same (try dragging vertices around to make the pictures match up), but the middle graph is different (which you can see, for example, by noting that the middle graph has only one vertex of degree 2, while the others have two such vertices).

### 2

Which of the graphs in the previous question contain Euler paths or circuits? Which of the graphs are planar?

**Solution**-
The first (and third) graphs contain an Euler path. All the graphs are planar.

### 3

Draw a graph which has an Euler circuit but is not planar.

**Solution**-
For example, \(K_5\text{.}\)

### 4

Draw a graph which does not have an Euler path and is also not planar.

**Solution**-
For example, \(K_{3,3}\text{.}\)

### 5

If a graph has 10 vertices and 10 edges and contains an Euler circuit, must it be planar? How many faces would it have?

**Solution**-
Yes. According to Euler's formula it would have 2 faces. It does. The only such graph is \(C_{10}\text{.}\)

### 6

Suppose \(G\) is a graph with \(n\) vertices, each having degree 5.

- For which values of \(n\) does this make sense?
- For which values of \(n\) does the graph have an Euler path?
- What is the smallest value of \(n\) for which the graph might be planar? (tricky)

**Solution**-
- Only if \(n \ge 6\) and is even.
- None.
- 12. Such a graph would have \(\frac{5n}{2}\) edges. If the graph is planar, then \(n - \frac{5n}{2} + f = 2\) so there would be \(\frac{4+3n}{2}\) faces. Also, we must have \(3f \le 2e\text{,}\) since the graph is simple. So we must have \(3\left(\frac{4 + 3n}{2}\right) \le 5n\text{.}\) Solving for \(n\) gives \(n \ge 12\text{.}\)

### 7

At a school dance, 6 girls and 4 boys take turns dancing (as couples) with each other.

- How many couples danced if every girl dances with every boy?
- How many couples danced if everyone danced with everyone else (regardless of gender)?
- Explain what graphs can be used to represent these situations.

**Solution**-
- There were 24 couples: 6 choices for the girl and 4 choices for the boy.
- There were 45 couples: \({10 \choose 2}\) since we must choose two of the 10 people to dance together.
- For part (a), we are counting the number of edges in \(K_{4,6}\text{.}\) In part (b) we count the edges of \(K_{10}\text{.}\)

### 8

Among a group of \(n\) people, is it possible for everyone to be friends with an odd number of people in the group? If so, what can you say about \(n\text{?}\)

**Solution**-
Yes, as long as \(n\) is even. If \(n\) were odd, then corresponding graph would have an odd number of odd degree vertices, which is impossible.

### 9

Your friend has challenged you to create a convex polyhedron containing 9 triangles and 6 pentagons.

- Is it possible to build such a polyhedron using
*only*these shapes? Explain. - You decide to also include one heptagon (seven-sided polygon). How many vertices does your new convex polyhedron contain?
- Assuming you are successful in building your new 16-faced polyhedron, could every vertex be the joining of the same number of faces? Could each vertex join either 3 or 4 faces? If so, how many of each type of vertex would there be?

**Solution**-
- No. The 9 triangles each contribute 3 edges, and the 6 pentagons contribute 5 edges. This gives a total of 57, which is exactly twice the number of edges, since each edge borders exactly 2 faces. But 57 is odd, so this is impossible.
- Now adding up all the edges of all the 16 polygons gives a total of 64, meaning there would be 32 edges in the polyhedron. We can then use Euler's formula \(v - e + f = 2\) to deduce that there must be 18 vertices.
- If you add up all the vertices from each polygon separately, we get a total of 64. This is not divisible by 3, so it cannot be that each vertex belongs to exactly 3 faces. Could they all belong to 4 faces? That would mean there were \(64/4 = 16\) vertices, but we know from Euler's formula that there must be 18 vertices. We can write \(64 = 3x + 4y\) and solve for \(x\) and \(y\) (as integers). We get that there must be 10 vertices with degree 4 and 8 with degree 3. (Note the number of faces joined at a vertex is equal to its degree in graph theoretic terms.)

### 10

Is there a convex polyhedron which requires 5 colors to properly color the vertices of the polyhedron? Explain.

**Solution**-
No. Every polyhedron can be represented as a planar graph, and the Four Color Theorem says that every planar graph has chromatic number at most 4.

### 11

How many edges does the graph \(K_{n,n}\) have? For which values of \(n\) does the graph contain an Euler circuit? For which values of \(n\) is the graph planar?

**Solution**-
\(K_{n,n}\) has \(n^2\) edges. The graph will have an Euler circuit when \(n\) is even. The graph will be planar only when \(n \lt 3\text{.}\)

### 12

The graph \(G\) has 6 vertices with degrees \(1, 2, 2, 3, 3, 5\text{.}\) How many edges does \(G\) have? If \(G\) was planar how many faces would it have? Does \(G\) have an Euler path?

**Solution**-
\(G\) has 8 edges (since the sum of the degrees is 16). If \(G\) is planar, then it will have 4 faces (since \(6 - 8 + 4 = 2\)). \(G\) does not have an Euler path since there are more than 2 vertices of odd degree.

### 13

What is the smallest number of colors you need to properly color the vertices of \(K_{7}\text{.}\) Can you say whether \(K_7\) is planar based on your answer?

**Solution**-
\(7\) colors. Thus \(K_7\) is not planar (by the contrapositive of the Four Color Theorem).

### 14

What is the smallest number of colors you need to properly color the vertices of \(K_{3,4}\text{?}\) Can you say whether \(K_{3,4}\) is planar based on your answer?

**Solution**-
The chromatic number of \(K_{3,4}\) is 2, since the graph is bipartite. You cannot say whether the graph is planar based on this coloring (the converse of the Four Color Theorem is not true). In fact, the graph is

*not*planar, since it contains \(K_{3,3}\) as a subgraph.

### 15

A dodecahedron is a regular convex polyhedron made up of 12 regular pentagons.

- Suppose you color each pentagon with one of three colors. Prove that there must be two adjacent pentagons colored identically.
- What if you use four colors?
- What if instead of a dodecahedron you colored the faces of a cube?

**Solution**-
For all these questions, we are really coloring the vertices of a graph. You get the graph by first drawing a planar representation of the polyhedron and then taking its planar dual: put a vertex in the center of each face (including the outside) and connect two vertices if their faces share an edge.

- Since the planar dual of a dodecahedron contains a 5-wheel, it's chromatic number is at least 4. Alternatively, suppose you could color the faces using 3 colors without any two adjacent faces colored the same. Take any face and color it blue. The 5 pentagons bordering this blue pentagon cannot be colored blue. Color the first one red. Its two neighbors (adjacent to the blue pentagon) get colored green. The remaining 2 cannot be blue or green, but also cannot both be red since they are adjacent to each other. Thus a 4th color is needed.
- The planar dual of the dodecahedron is itself a planar graph. Thus by the 4-color theorem, it can be colored using only 4 colors without two adjacent vertices (corresponding to the faces of the polyhedron) being colored identically.
- The cube can be properly 3-colored. Color the “top” and “bottom” red, the “front” and “back” blue, and the “left” and “right” green.

### 16

If a planar graph \(G\) with \(7\) vertices divides the plane into 8 regions, how many edges must \(G\) have?

**Solution**-
\(G\) has \(13\) edges, since we need \(7 - e + 8 = 2\text{.}\)

### 17

Consider the graph below:

- Does the graph have an Euler path or circuit? Explain.
- Is the graph planar? Explain.
- Is the graph bipartite? Complete? Complete bipartite?
- What is the chromatic number of the graph.

**Solution**-
- The graph does have an Euler path, but not an Euler circuit. There are exactly two vertices with odd degree. The path starts at one and ends at the other.
- The graph is planar. Even though as it is drawn edges cross, it is easy to redraw it without edges crossing.
- The graph is not bipartite (there is an odd cycle), nor complete.
- The chromatic number of the graph is 3.

### 18

For each part below, say whether the statement is true or false. Explain why the true statements are true, and give counterexamples for the false statements.

- Every bipartite graph is planar.
- Every bipartite graph has chromatic number 2.
- Every bipartite graph has an Euler path.
- Every vertex of a bipartite graph has even degree.
- A graph is bipartite if and only if the sum of the degrees of all the vertices is even.

**Solution**-
- False. For example, \(K_{3,3}\) is not planar.
- True. The graph is bipartite so it is possible to divide the vertices into two groups with no edges between vertices in the same group. Thus we can color all the vertices of one group red and the other group blue.
- False. \(K_{3,3}\) has 6 vertices with degree 3, so contains no Euler path.
- False. \(K_{3,3}\) again.
- False. The sum of the degrees of all vertices is even for
*all*graphs so this property does not imply that the graph is bipartite.

### 19

Consider the statement “If a graph is planar, then it has an Euler path.”

- Write the converse of the statement.
- Write the contrapositive of the statement.
- Write the negation of the statement.
- Is it possible for the contrapositive to be false? If it was, what would that tell you?
- Is the original statement true or false? Prove your answer.
- Is the converse of the statement true or false? Prove your answer.

**Solution**-
- If a graph has an Euler path, then it is planar.
- If a graph does not have an Euler path, then it is not planar.
- There is a graph which is planar and does not have an Euler path.
- Yes. In fact, in this case it is because the original statement is false.
- False. \(K_4\) is planar but does not have an Euler path.
- False. \(K_5\) has an Euler path but is not planar.

### 20

Remember that a tree is a connected graph with no cycles.

- Conjecture a relationship between a tree graph's vertices and edges. (For instance, can you have a tree with 5 vertices and 7 edges?)
- Explain why every tree with at least 3 vertices has a leaf (i.e., a vertex of degree 1).
- Prove your conjecture from part (a) by induction on the number of vertices. Hint: For the inductive step, you will assume that your conjecture is true for all trees with \(k\) vertices, and show it is also true for an arbitrary tree with \(k+1\) vertices. Consider what happens when you cut off a leaf and then let it regrow.