FREE! Click here to Join FunTrivia. Thousands of games, quizzes, and lots more!
Quiz about Basics of Graph Theory
Quiz about Basics of Graph Theory

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.
  1. Home
  2. »
  3. Quizzes
  4. »
  5. Science Trivia
  6. »
  7. Math
  8. »
  9. Specific Math Topics

Author
diamondback1
Time
5 mins
Type
Multiple Choice
Quiz #
318,264
Updated
Dec 03 21
# Qns
10
Difficulty
Tough
Avg Score
6 / 10
Plays
439
Last 3 plays: Guest 41 (7/10), Guest 112 (7/10), Guest 175 (6/10).
- -
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


Question 2 of 10
2. All graphs must have edges.


Question 3 of 10
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


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


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


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


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


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


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


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



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

arrow Select a User ID:
arrow Choose a Password:
arrow Your Email:




Most Recent Scores
Mar 27 2024 : Guest 41: 7/10
Mar 17 2024 : Guest 112: 7/10
Mar 15 2024 : Guest 175: 6/10
Feb 21 2024 : Guest 106: 3/10
Feb 14 2024 : Guest 112: 1/10
Feb 07 2024 : Guest 102: 2/10
Feb 06 2024 : Guest 160: 6/10
Feb 05 2024 : Guest 106: 4/10

Score Distribution

quiz
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.
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.)

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.
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?

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.
Related Quizzes
1. Math: Exponents Average
2. A quiz on Pi Average
3. Euler's Number and Euler's Constant Tough
4. The (Mis) Adventures of Miss Polly Nomial Tough
5. Vectors Average
6. Square Numbers Average
7. Palindromic Numbers Average
8. The Number Pi Average
9. Zero... A Number? Average
10. Odd or Even? Average
11. Fibonacci Numbers Average
12. Fractions Tough

3/28/2024, Copyright 2024 FunTrivia, Inc. - Report an Error / Contact Us