Graph Theory Trivia Quiz

Answer: Leonhard Euler

Apart from graph theory, Euler also made great contribution in the field of calculus. The irrational number, e (2.71828...) is named after him.

Answer: 7

Konigsberg is a Russian city (formerly known as Prussian).

In the Seven Bridges of Konigsberg problem, there are two islands (island A and island B) that are connected to the mainland by several bridges. Island A is connected to the mainland by 4 bridges (2 bridges to the north and 2 bridges to the south). On the other hand, island B is connected to the mainland by a bridge to the south and another bridge to the north.

In addition, the two islands are connected together by another bridge. So, there are all together seven bridges.

Provided that one can start and end anywhere, can he or she cross all bridges without crossing any bridge twice? Euler proved that it is impossible to accomplish the task.

Answer: Edge

The vertices are the individual "points" of the graph. The edges refer to the "lines" joining these vertices. Let's say there is a line joining the points v1 and v2. So, these v1 and v2 are the 2 vertices of the graph. The line is called the edge of the graph.

For example, a graph G with 3 vertices and 4 edges can be denoted by the notation G = (V, E), where V = {v1, v2, v3} and E = {e1, e2, e3, e4}.

Answer: Multigraphs

By definition, a simple graph is a graph that does not contain any loops and multiple edges.

As the name suggests, a multigraph allows both loops and multiple edges. A loop is an edge that starts from and ends with the same vertex. In other words, the initial point and the ending point is the same.

The alternative name for multiple edge is parallel edge. Let's denote two vertices as v1 and v2. And there are two edges, e1 and e2 connecting them. These two edges are known as the multiple edges of the graph.

Answer: Digraphs

An undirected graph consists of non-ordered pairs but a directed graph consists of ordered pairs.

For an undirected graph, e1 = {v1, v2} is the same as e2 = {v2, v1}. However, this is not the case for edges in a directed graph.

Directed graphs are more useful where it comes to the study and application of road traffic. Here's an analogy - a two-way road can be visualized as an undirected graph while a one-way road is a directed graph.

Answer: 2

The Star of David appears on the Israel's flag. It consists of 2 overlapping triangles, one pointing upwards and the other one downwards.

Each of the six points of the star is a vertex. Notice that there are 2 lines jutting out from from the point. These 2 lines are the edges that are incident with the vertex. So deg (v) = 2.

Answer: 1 + 2 + ... + 8 + 9 = 45

Multiple edges or parallel edges are not allowed in a simple graph. In other words, there is only one line (edge) that can be drawn to join two different vertices. Also, loops are not allowed in a simple graph.

Let's say the ten vertices are {v1, v2, ..., v9, v10}. The total number of lines that can be drawn is C (10, 2) = 45. In other words, there are all together 45 ways to choose 2 different vertices out of the given 10 vertices.

Answer: Twice

Let's say there are 2 vertices v1 and v2 for a graph G. And there is a line (or edge) joining these 2 vertices. So, deg (v1) = 1 and similarly, deg (v2) = 1. Therefore, the degree sum for the graph. deg (v) = deg (v1) + deg (v2) = 1 + 1 = 2, which is twice the number of edges of the graph.

The reason behind this theorem is that each edge is counted twice as illustrated in the example above.

Answer: Four

The four color theorem was first proposed by the South African mathematician, Francis Guthrie while he studied the map of counties of England. He noticed that only four colors were needed to distinguish one county from its neighboring one. Guthrie wondered if this was also the case for any other 2-D regions or planes.

This theorem is unique in a way that it can be proved by computers. However, this so-called computer-assisted proof is not preferred by most mathematicians because some of the steps and algorithms that are performed by the machines are not verifiable by humans.

Answer: All of these

In computer science, a programmer might want to write a source code which takes less time to execute a task in order to save time and also increase efficiency.

Furthermore, the complicated structures of molecules are studied extensively by biologists, chemists and physicists. With the help of graph theory, the topology of certain molecules can be studied in a systematic way.

Network analysis involves the study and calculation of voltage, current and resistance in electrical circuits. It is also used in operations research, economic, sociology and other fields.