FREE! Click here to Join FunTrivia. Thousands of games, quizzes, and lots more!

Basics of Graph Theory Trivia Quiz

Despite its misleading name, graph theory doesn't pertain to graphs of equations. Instead, it is a branch of pure mathematics. This quiz discusses some basic elements of graph theory, referencing R. Trudeau's "Introduction to Graph Theory."

A multiple-choice quiz by diamondback1. Estimated time: 5 mins.

Author
diamondback1

Time
5 mins

Type
Multiple Choice

Quiz #
318,264

Updated
Dec 03 21

# Qns
10

Difficulty
Tough

Avg Score
6 / 10

Plays
461

Last 3 plays: Guest 131 (7/10), calmdecember (4/10), Guest 133 (5/10).

One at a Time - Single Page - Timed Game

Question 1 of 10

1. When a vertex Q is connected by an edge to a vertex K, what is the term for the relationship between Q and K? Hint

Q and K are "insecure."

Q and K are "incident."

Q and K are "adjacent."

Q and K are "isolated."

NEXT>

Question 2 of 10

2. All graphs must have edges.

True

False

3. In graph theory, it is possible that two graphs might look (at least to the uneducated eye) exceedingly dissimilar, yet in actuality be equal. How can we determine whether or not two graphs are equal? (Make sure your answer is true in ALL cases.) Hint

Two graphs are equal if there is a one-to-one correspondence between their vertex sets, so that when two vertices of one graph are adjacent, the corresponding vertices of the other graph are adjacent.

Two graphs are equal if they have equal vertex sets and equal edge sets.

Two graphs are equal if they contain the same number of vertices and edges.

Trick question; equal graphs are always drawn in such a way that they immediately appear equal.

NEXT>

Question 4 of 10

4. Isomorphism is similar to equality, but more general. Of the following common graphs, which two are isomorphic? Hint

The cyclic graph on five vertices and the wheel graph on five vertices.

The path graph on four vertices and the complete graph on four vertices.

The cyclic graph on three vertices and the complete graph on three vertices.

The utility graph and the complete graph on six vertices.

NEXT>

Question 5 of 10

5. The complete graph, denoted Kv (where v represents the number of vertices, and v is a positive integer), is the graph having all possible edges. In other words, each vertex in Kv is connected to all of the other vertices in Kv. One can determine the number of edges in Kv by counting, but it is much easier to use a formula! Which of the following formulas gives the number of edges (e) of the complete graph on v vertices? Hint

e = 2(v-1)

e = 2(v+1)

e = v-1

e = (1/2)v(v-1)

NEXT>

Question 6 of 10

6. In graph theory, a graph X is a "complement" of a graph F if which of the following is true? (Make sure your answer is true in ALL cases.) Hint

If X is equal to F, then X is a complement of F.

If X has half of the vertices of F (or if F has half of the vertices of X) then X is a complement of F.

If X is NOT equal to F, then X is a complement of F.

If X has the same vertex set as F, and as its edges ONLY all possible edges NOT contained in F, then X is a complement of F.

NEXT>

Question 7 of 10

7. An isomorphism can be proven between a graph T and a graph B if their complements are isomorphic.

True

False

NEXT>

Question 8 of 10

8. Which of the following are you NOT allowed to do when creating an expansion of a graph? Hint

"Splice" a single vertex onto a place where two or more edges intersect, so that all of those edges now share the new vertex.

"Splice" a single vertex into an edge, creating a new vertex and a new edge.

Leave the graph unaltered.

"Splice" more than one vertex into an edge, creating one new edge per new vertex.

NEXT>

Question 9 of 10

9. Which of the following graphs can be drawn without edge crossings? Hint

The wheel graph on ten vertices.

The complete graph on six vertices.

The complete graph on five vertices.

The utility graph.

NEXT>

Question 10 of 10

10. There are thirty-four possible (not isomorphic) graphs with five vertices. Which of the following graphs is isomorphic to its OWN compliment? Hint

The null graph on five vertices.

The complete graph on five vertices.

The cyclic graph on five vertices.

The path graph on five vertices.

(Optional) Create a Free FunTrivia ID to save the points you are about to earn:

Select a User ID:

Choose a Password:

Your Email:

Most Recent Scores

Oct 24 2024 : Guest 131: 7/10
Oct 22 2024 : calmdecember: 4/10
Oct 13 2024 : Guest 133: 5/10
Oct 10 2024 : Guest 141: 7/10
Sep 30 2024 : callie_ross: 1/10

Score Distribution

Quiz Answer Key and Fun Facts

1. When a vertex Q is connected by an edge to a vertex K, what is the term for the relationship between Q and K?

Answer: Q and K are "adjacent."

Vertices Q and K are adjacent. The edge connecting Q and K would be considered "incident" to both Q and K. A vertex that is not incident to any edges at all is "isolated." The term "insecure," on the other hand, has absolutely nothing to do with graph theory!

2. All graphs must have edges.

Answer: False

This is false. Although all graphs must have vertices, null graphs (designated Nv, where v is the number of vertices) contain no edges. You may have an infinite number of vertices, and no edges whatsoever.

Answer: Two graphs are equal if they have equal vertex sets and equal edge sets.

This question is somewhat tricky, but only one answer is correct. Although equal graphs certainly must have the same number of edges and vertices, two graphs that have the same number of edges and vertices do not have to be equal. If, for two graphs, there is "a one-to-one correspondence between their vertex sets, so that when two vertices of one graph are adjacent, the corresponding vertices of the other graph are adjacent" then the two graphs are isomorphic-and not necessarily equal.

REMEMBER: All graphs that are equal must be isomorphic, but graphs that are isomorphic need not be equal!

4. Isomorphism is similar to equality, but more general. Of the following common graphs, which two are isomorphic?

Answer: The cyclic graph on three vertices and the complete graph on three vertices.

The cyclic graph on three vertices and the complete graph on three vertices have a "one-to-one correspondence between their vertex sets, so that when two vertices of one graph are adjacent, the corresponding vertices of the other graph are adjacent," and thus are isomorphic. Both contain three vertices, each of which is connected to the other two vertices. None of the other three sets are isomorphic.

Answer: e = (1/2)v(v-1)

The formula e = (1/2)v(v-1) can be used to find the number of edges of Kv. For example, the complete graph on five vertices gives us e = (1/2) 5 (4), which gives us e = 10. The number of edges of the complete graph can easily be counted manually, and there are in fact 10. Note: this is not a proper "proof", merely an example!

By the way, e = v-1 gives us the number of edges in the path graph on v vertices (Pv) and e = 2(v-1) gives us the number of edges in the wheel graph on v vertices (Wv).

6. In graph theory, a graph X is a "complement" of a graph F if which of the following is true? (Make sure your answer is true in ALL cases.)

Answer: If X has the same vertex set as F, and as its edges ONLY all possible edges NOT contained in F, then X is a complement of F.

Remember, a graph is not usually, if ever, equal to its complement (though it may occasionally be isomorphic to it) but the mere fact that two graphs are unequal does NOT make them complementary. The trick is to keep in mind that just because a relationship in graph theory may in some cases be true, does not mean it is true by necessity!

7. An isomorphism can be proven between a graph T and a graph B if their complements are isomorphic.

Answer: True

Correct! Conversely, if the compliments of T and B are NOT isomorphic, then T and B are not isomorphic. This can be especially useful when two graphs have many edges, because the complement may be far less cluttered, making it easier to spot whether or not the two graphs are isomorphic.

8. Which of the following are you NOT allowed to do when creating an expansion of a graph?

Answer: "Splice" a single vertex onto a place where two or more edges intersect, so that all of those edges now share the new vertex.

When creating an expansion, you are allowed to add an infinite number new vertices to the existing edges, as long as NO new vertex has more than two degrees (degrees are the number of edges incident to a particular vertex.) Also, by definition, any graph is an expansion of itself, so you may leave a graph unaltered and still have an expansion.

9. Which of the following graphs can be drawn without edge crossings?

Answer: The wheel graph on ten vertices.

The wheel graph, Wv, can be drawn without edge crossings. Drawing the complete graph on five vertices or the utility graph without edge crossings is impossible, which can be proved by the Jordan Curve Theorem. Similarly, the complete graph on ten vertices contains the complete graph on five vertices (and possibly UG-try to find it yourself, if you feel inclined!) as a subgraph, and thus cannot be drawn without edge crossings either.

10. There are thirty-four possible (not isomorphic) graphs with five vertices. Which of the following graphs is isomorphic to its OWN compliment?

Answer: The cyclic graph on five vertices.

The cyclic graph on five vertices is the only cyclic graph isomorphic to its own compliment.

The number of possible (not isomorphic) graphs for any v (when v represents the number of vertices) climbs rapidly. There might be only thirty-four possible graphs on five vertices, but there are three hundred and eight thousand, seven hundred and eight possible graphs on nine vertices. Yikes!

Source: Author diamondback1

This quiz was reviewed by FunTrivia editor crisw before going online.
Any errors found in FunTrivia content are routinely corrected through our feedback system.