maths.free › Combinatorics & Graph Theory › 3. Graph Theory › Problems and Definitions

Problems and Definitions

Investigation In the time of Euler, in the town of Königsberg in Prussia, there was a river containing two islands. The islands were connected to the banks of the river by seven bridges (as seen below).

Section Preview

Investigation

In the time of Euler, in the town of Königsberg in Prussia, there was a river containing two islands. The islands were connected to the banks of the river by seven bridges (as seen below). The bridges were very beautiful, and on their days off, townspeople would spend time walking over the bridges. As time passed, a question arose: Was it possible to plan a walk so that you cross each bridge once and only once? Euler was able to answer this question. Are you?

Graph Theory is a relatively new area of mathematics, first studied by the super famous mathematician Leonhard Euler in 1735. Since then it has blossomed into a powerful tool used in nearly every branch of science and is currently an active area of mathematics research.

The problem above, known as the Seven Bridges of Königsberg, is the problem that originally inspired graph theory. Consider a different problem: Below is a drawing of four dots connected by some lines. Is it possible to trace over each line once and only once (without lifting your pencil, starting and ending on a dot)?

There is an obvious connection between these two problems. Any path in the dot and line drawing corresponds exactly to a path over the bridges of Königsberg.

Pictures like this dot and line drawing are called graphs (although technically, the picture above is a multigraph). Graphs are made up of a collection of dots called vertices and lines connecting those dots called edges. When two vertices are connected by an edge, we say they are adjacent. The nice thing about looking at graphs instead of pictures of rivers, islands, and bridges is that we now have a mathematical object to study. We have distilled the important parts of the bridge picture for the problem. It does not matter how big the islands are, what the bridges are made out of, if the river contains alligators, etc. All that matters is which land masses are connected to which other land masses, and how many times. This was the great insight Euler had.

We will return to the question of finding paths through graphs in . In this section, we will explore various ways that graphs can be used to represent, or model, real-world problems. Along the way, we will introduce some basic definitions, terminology, and notation that will be used in the rest of the chapter.

What is a Graph?

Before we start studying graphs, we need to agree upon what a graph is. While we almost always think of graphs as pictures (dots connected by lines), this is fairly ambiguous. Do the lines need to be straight? Does it matter how long the lines are or how large the dots are? Can there be two lines connecting the same pair of dots? Can one line connect three dots?

The way we avoid ambiguities in mathematics is to provide concrete and rigorous definitions. Crafting good definitions is not easy, but it is incredibly important. The definition is the agreed-upon starting point from which all truths in mathematics proceed. Is there a graph with no edges? We have to look at the definition to see if this is possible.

We want our definition to be precise and unambiguous, but it also must agree with our intuition for the objects we are studying. It needs to be useful: We could define a graph to be a six-legged mammal, but that would not let us solve any problems about bridges. Instead, here is the (now) standard definition of a graph.

Strange. Nowhere in the definition is there talk of dots or lines. From the definition, a graph could be \[(\{a,b,c,d\}, \{\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\}\})\]. Here we have a graph with four vertices (the letters \(a, b, c, d\)) and five edges (the pairs \(\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\})\)).

Looking at sets and sets of 2-element sets is difficult to process. That is why we often draw a representation of these sets. We put a dot down for each vertex, and connect two dots with a line precisely when those two vertices are one of the 2-element subsets in our set of edges. Thus one way to draw the graph described above is this:

However we could also have drawn the graph differently. For example either of these:

We should be careful about what it means for two graphs to be the same. Actually, given our definition, this is easy: Are the vertex sets equal? Are the edge sets equal? We know what it means for sets to be equal, and graphs are nothing but a pair of two special sorts of sets.

Even if two graphs are not equal, they might be basically the same. The graphs in the previous example could be drawn like this:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (23)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

Is there more than one graph with five vertices and six edges? Explain what this question even means and how you would answer it.
What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.
Consider the graph \(G\) below.
Which of the following graphs are isomorphic to \(G\)? Select all that apply.
Жауап беріңіз

The graphs in (a) and (c) are isomorphic to \(G\).
Which of the following graphs are isomorphic to each other?
Жауап беріңіз

Graphs (a) and (c) are isomorphic to each other. So are graphs (b) and (d).
The graph \(G_1\) has 8 vertices all of degree 6. How many edges does \(G_1\) have?
The graph \(G_2\) has 7 vertices all of degree k, and 7 edges. What is \(k\)?
The graph \(G_3\) has all vertices of degree 4, and \(16\) edges. How many vertices does \(G_3\) have?

Жауап беріңіз

\(G_1\) has 24 edges. \(k = 2\) for \(G_2\). \(G_3\) has 8 vertices.
Suppose a graph has degree sequence \((8,7,7,6,6,6,5,4,4,3)\). How many edges must the graph have?

Жауап беріңіз

The graph must have 29 edges.
1. What is the largest \(n\) such that \(P_n\) is a subgraph of \(K_{5}\)?
2. What is the largest \(n\) such that \(C_n\) is a subgraph of \(K_{5}\)?
3. What is the largest \(n\) such that \(P_n\) is an induced subgraph of \(K_{5}\)?
4. What is the largest \(n\) such that \(C_n\) is an induced subgraph of \(K_{5}\)?
Жауап беріңіз
Hint:
Remember that \(P_n\) is the path that contains \(n\) edges and \(n+1\) vertices.
1. \(n\)\(P_n\)\(K_{5}\)
2. \(n\)\(C_n\)\(K_{5}\)
3. \(n\)\(P_n\)induced\(K_{5}\)
4. \(n\)\(C_n\)induced\(K_{5}\)
If 10 people each shake hands with each other, how many handshakes took place? What does this question have to do with graph theory?

Жауап беріңіз

This is asking for the number of edges in \(K_{10}\). Each vertex (person) has degree (shook hands with) 9 (people). So the sum of the degrees is \(90\). However, the degrees count each edge (handshake) twice, so there are 45 edges in the graph. That is how many handshakes took place.
Among a group of 5 people, is it possible for everyone to be friends with exactly 2 of the people in the group? What about 3 of the people in the group?

Жауап беріңіз

It is possible for everyone to be friends with exactly 2 people. You could arrange the 5 people in a circle and say that everyone is friends with the two people on either side of them (so you get the graph \(C_5\)). However, it is not possible for everyone to be friends with 3 people. That would lead to a graph with an odd number of odd degree vertices which is impossible since the sum of the degrees must be even.
Is it possible for two different (non-isomorphic) graphs to have the same number of vertices and the same number of edges? What if the degrees of the vertices in the two graphs are the same (so both graphs have vertices with degrees 1, 2, 2, 3, and 4, for example)? Draw two such graphs or explain why not.

Жауап беріңіз

Hint:
Both situations are possible. Go find some examples.
Are the two graphs below equal? Are they isomorphic? If they are isomorphic, give the isomorphism. If not, explain.
Graph 1: \(V = \{a,b,c,d,e\}\), \(E = \{\{a,b\}, \{a,c\}, \{a,e\}, \{b,d\}, \{b,e\}, \{c,d\}\}\) .
Graph 2:

Жауап беріңіз

The graphs are not equal. For example, graph 1 has an edge \(\{a,b\}\), but graph 2 does not have that edge. They are isomorphic. One possible isomorphism is \(f:G_1 \to G_2\) defined by \(f(a) = d\), \(f(b) = c\), \(f(c) = e\), \(f(d) = b\), \(f(e) = a\).
Consider the following two graphs:
- \(G_1\)
  \(V_1=\{a,b,c,d,e,f,g\}\)
  \(E_1=\{\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{b,e\},\)
  \(\quad\{b,f\},\{c,g\},\{d,e\}, \{e,f\},\{f,g\}\}\).
- \(G_2\)
  \(V_2=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}\),
  \(E_2=\{\{v_1,v_4\},\{v_1,v_5\},\{v_1,v_7\},\{v_2,v_3\},\{v_2,v_6\},\)
  \(\quad\{v_3,v_5\},\{v_3,v_7\},\{v_4,v_5\},\{v_5,v_6\},\{v_5,v_7\}\}\).
1. Let \(f:G_1 \rightarrow G_2\) be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is given by the following table:
  \(x\) \(a\) \(b\) \(c\) \(d\) \(e\) \(f\) \(g\)
  \(f(x)\) \(v_4\) \(v_5\) \(v_1\) \(v_6\) \(v_2\) \(v_3\) \(v_7\)
  Does \(f\) define an isomorphism between Graph 1 and Graph 2?
2. Define a new function \(g\) (with \(g \ne f\)) that defines an isomorphism between Graph 1 and Graph 2.
3. Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain.
What is the largest number of edges possible in a graph with 10 vertices? What is the largest number of edges possible in a bipartite graph with 10 vertices? What is the largest number of edges possible in a tree with 10 vertices?

Жауап беріңіз

Hint:
The bipartite graph is a little tricky. You will definitely want a complete bipartite graph, but it could be \(K_{5,5}\) or maybe \(K_{1,9}\), or
Which of the graphs below are bipartite? Justify your answers.

Жауап беріңіз

Hint:
The first graph is bipartite, which can be seen by labeling it as follows.
Two of the remaining three are also bipartite.
For which \(n \ge 3\) is the graph \(C_n\) bipartite?

Жауап беріңіз

Hint:
\(C_4\) is bipartite; \(C_5\) is not. What about all the other values of \(n\)?
For each of the following, try to give two different unlabeled graphs with the given properties, or explain why doing so is impossible.
1. Two different trees with the same number of vertices and the same number of edges. A tree is a connected graph with no cycles.
2. Two different graphs with 8 vertices all of degree 2.
3. Two different graphs with 5 vertices all of degree 4.
4. Two different graphs with 5 vertices all of degree 3.
Жауап беріңіз
1. For example:
2. This is not possible if we require the graphs to be connected. If not, we could take \(C_8\) as one graph and two copies of \(C_4\) as the other.
3. Not possible. If you have a graph with 5 vertices all of degree 4, then every vertex must be adjacent to every other vertex. This is the graph \(K_5\).
4. This is not possible. In fact, there is not even one graph with this property (such a graph would have \(5\cdot 3/2 = 7.5\) edges).
Decide whether the statements below about subgraphs are true or false. For those that are true, briefly explain why (1 or 2 sentences). For any that are false, give a counterexample.
1. Any subgraph of a complete graph is also complete.
2. Any induced subgraph of a complete graph is also complete.
3. Any subgraph of a bipartite graph is bipartite.
4. Any subgraph of a tree is a tree.
Жауап беріңіз
1. False.
2. True.
3. True.
4. False.
We often define graph theory concepts using set theory. For example, given a graph \(G = (V, E)\) and a vertex \(v \in V\), we define \[N(v) = \{u \in V \st \{v,u\} \in E\}\]. We define \(N[v] = N(v) \cup \{v\}\). The goal of this problem is to figure out what all this means.
1. Let \(G\) be the graph with vertices \(V\) and edges \(E\) given by \[V = \{a,b,c,d,e,f\},~~E = \{\{a,b\}, \{a,e\},\{b, c\}, \{b,e\}, \{c,d\}, \{c, f\}, \{d, f\}, \{e,f\}\}\]. Find \(N(a)\), \(N[a]\), \(N(c)\), and \(N[c]\).
2. What are the largest and smallest possible values for \(|N(v)|\) and \(|N[v]|\) (the sizes of these sets) for the graph in part (a)? Explain.
3. Give an example of a graph \(G = (V, E)\) (probably different from the one above) for which \(N[v] = V\) for some vertex \(v \in V\). Is there a graph for which \(N[v] = V\) for all \(v \in V\)? Explain.
4. Give an example of a graph \(G = (V,E)\) for which \(N(v) = \emptyset\) for some \(v \in V\). Is there an example of such a graph for which \(N[u] = V\) for some other \(u \in V\) as well? Explain.
5. Describe in words what \(N(v)\) and \(N[v]\) mean in general.
Жауап беріңіз

Hint:
You should be able to deduce everything directly from the definition. However, perhaps it would be helpful to know that the \(N\) stands for neighborhood.
A graph is a way of representing the relationships between elements in a set: An edge between the vertices \(x\) and \(y\) tells us that \(x\) is related to \(y\) (which we can write as \(x \sim y\)). Not all sorts of relationships can be represented by a graph, though. For each relationship described below, either draw the graph or explain why the relationship cannot be represented by a graph.
1. The set \(V = \{1,2, \ldots, 9\}\) and the relationship \(x \sim y\) when \(x-y\) is a non-zero multiple of 3.
2. The set \(V = \{1,2, \ldots, 9\}\) and the relationship \(x \sim y\) when \(y\) is a multiple of \(x\).
3. The set \(V = \{1,2,\ldots, 9\}\) and the relationship \(x \sim y\) when \(0 \lt |x-y| \lt 3\).
Жауап беріңіз

Hint:
Be careful to make sure the edges are not directed. In a graph, if \(a\) is adjacent to \(b\), then \(b\) is adjacent to \(a\). In the language of relations, we say that the edge relation is symmetric.
Consider graphs with \(n\) vertices. Remember, graphs do not need to be connected.
1. How many edges must the graph have to guarantee at least one vertex has degree two or more? Prove your answer.
2. How many edges must the graph have to guarantee all vertices have degree two or more? Prove your answer.
Жауап беріңіз

Hint:
You might want to answer the questions for some specific values of \(n\) to get a feel for them, but your final answers should be in terms of \(n\).
Prove that any graph with at least two vertices must have two vertices of the same degree.

Жауап беріңіз

Hint:
Try a small example first: Any graph with 8 vertices must have two vertices of the same degree. If not, what would the degree sequence be?
Suppose \(G\) is a connected graph with \(n > 1\) vertices and \(n-1\) edges. Prove that \(G\) has a vertex of degree 1.

Жауап беріңіз

Hint:
Use the handshake lemma. What would happen if all the vertices had degree 2?
Which (if any) of the graphs below are the same?
The graphs above are unlabeled. Usually we think of a graph as having a specific set of vertices. Which (if any) of the graphs below are the same?
Actually, all the graphs above are just drawings of graphs. A graph is really an abstract mathematical object consisting of two sets \(V\) and \(E\), where \(E\) is a set of 2-element subsets of \(V\). Are the graphs below the same or different?
- Graph 1:
  \(V = \{a, b, c, d, e\}\),
  \(E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}\) .
- Graph 2:
  \(V = \{v_1, v_2, v_3, v_4, v_5\}\),
  \(E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\).

Symbols used here

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

How to: Problems and Definitions

Use the language of graph theory to describe properties of graphs.
Utilize multiple representations of graphs.
Apply the Handshake Lemma to answer questions about graphs and problems they represent.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Өзіңіздіңіңізді сынап көріңіз

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Келесіде Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion–exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs

\(x\)	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)	\(f\)	\(g\)
\(f(x)\)	\(v_4\)	\(v_5\)	\(v_1\)	\(v_6\)	\(v_2\)	\(v_3\)	\(v_7\)