Unlock hundreds more features
Save your Quiz to the Dashboard
View and Export Results
Use AI to Create Quizzes and Analyse Results

OR
Sign inSign in with Facebook
Sign inSign in with Google
Quizzes > Mathematics

Graph Theory Quiz: Fundamentals and Core Concepts

Quick graph fundamentals quiz to check your understanding. Instant results.

Editorial: Review CompletedCreated By: Gyanraj ChavanUpdated Aug 23, 2025
Difficulty: Moderate
Questions: 20
Learning OutcomesStudy Material
Colorful paper art depicting elements of a Graph Theory Fundamentals Quiz

This graph theory quiz helps you practice the fundamentals, from vertices and edges to paths, traversals, and connectivity. Answer 15 multiple-choice questions and see instant feedback so you know what to review next. For a broader foundation, try our discrete math quiz or continue with a finite math quiz.

In graph theory, what is a vertex?
A node in the graph
A connection between two nodes
A cyclical path
A sequence of edges
A vertex, also called a node, is a fundamental unit in a graph representing an entity. It is not a path or sequence of edges, which are different graph components.
What best describes an edge in a graph?
A connection between two vertices
A traversal algorithm
A complete subgraph
A single vertex with a loop
An edge is defined as the link or connection between two vertices in a graph. It is not a traversal method or a subgraph, which are separate concepts.
Which characteristic defines a directed graph?
Every vertex is connected to every other vertex
Edges have no orientation
Edges have a specific orientation from one vertex to another
Graph has no cycles
A directed graph, or digraph, features edges with a defined direction from one vertex to another. The other options describe undirected graphs, acyclic graphs, and complete graphs, respectively.
What is true for an undirected graph?
Edges do not have an orientation
It cannot contain self-loops
Each edge has a unique direction
Edges must form a cycle
In an undirected graph, edges connect vertices without any direction, meaning the relationship is bidirectional. Undirected graphs can contain cycles or self-loops unless otherwise restricted.
When are two vertices considered adjacent in a graph?
When there is an edge directly connecting them
When they are in the same component but not directly connected
When they belong to different graphs
When they have the same degree
Two vertices are adjacent if there is a direct edge between them. Having the same degree or being in the same component without a direct edge does not make vertices adjacent.
Which condition makes a graph connected?
It has an equal number of vertices and edges
There is a path between every pair of vertices
It contains at least one cycle
All vertices have the same degree
A graph is connected if every pair of vertices is linked by some path. Cycles or vertex degrees do not guarantee connectivity, and equal counts of vertices and edges are unrelated to this property.
Which algorithm should you use to find the shortest path in a weighted graph with no negative edge weights?
Depth-first search
Prim's algorithm
Kruskal's algorithm
Dijkstra's algorithm
Dijkstra's algorithm efficiently finds the shortest paths in graphs with non-negative edge weights. DFS is a traversal method, while Kruskal's and Prim's algorithms are for minimum spanning trees, not shortest paths.
In a breadth-first search (BFS), which data structure is primarily used to manage the vertices to be explored?
Priority queue
Queue
Stack
Hash table
BFS uses a queue to process vertices in the order they are discovered, ensuring the shortest-path layering in unweighted graphs. A stack is characteristic of DFS, and priority queues or hash tables serve different purposes.
To find the minimum number of edges between two vertices in an unweighted graph, which algorithm is most appropriate?
Dijkstra's algorithm
Bellman-Ford algorithm
Breadth-first search
Depth-first search
BFS naturally finds the shortest path in terms of edge count in unweighted graphs. DFS does not guarantee minimal paths, and Dijkstra's and Bellman-Ford handle weighted scenarios.
What is the number of edges in a tree with n vertices?
n
n + 1
2n - 1
n - 1
A tree is an acyclic connected graph, and it always has exactly n - 1 edges for n vertices. Any other count implies either disconnected components or the presence of a cycle.
Which statement best defines a planar graph?
It has no cycles
It can be drawn on a plane without edge crossings
All vertices have degree at most 3
It is complete
Planar graphs can be embedded in the plane so that edges intersect only at their endpoints. The other options describe acyclic graphs, degree constraints, and completeness, which are unrelated to planarity.
Which graph representation typically uses O(V + E) space, where V is the number of vertices and E is the number of edges?
Adjacency matrix
Adjacency list
Edge list with duplicates
Incidence matrix
An adjacency list stores each vertex's neighbors, leading to O(V + E) space complexity. An adjacency matrix uses O(V^2), and incidence matrices and poorly structured edge lists have different complexities.
When are two graphs considered isomorphic?
They both are trees
They have the same number of vertices regardless of edge structure
There exists a one-to-one mapping between vertices that preserves adjacency
They have identical degree sequences only
Graph isomorphism requires a bijective vertex mapping that keeps edge connections the same. Simply having the same vertex count, being trees, or matching degree sequences without preserving connections does not guarantee isomorphism.
Which graph representation allows O(1) time complexity to check if an edge exists between two vertices?
Adjacency list
Edge list
Incidence list
Adjacency matrix
With an adjacency matrix, presence or absence of an edge can be checked by a single matrix lookup. Adjacency lists or edge lists require searching through a list of neighbors, leading to higher time complexity.
What property must a directed graph have to guarantee a topological ordering?
It must be strongly connected
It must have equal in-degree and out-degree for each vertex
It must be complete
It must be acyclic
Topological sorting is possible precisely for directed acyclic graphs (DAGs). Strong connectivity, completeness, or balanced degrees do not ensure the absence of cycles necessary for a topological order.
Which algorithm can compute shortest paths in a graph that contains negative edge weights but no negative cycles?
Prim's algorithm
Bellman-Ford algorithm
Dijkstra's algorithm
Kruskal's algorithm
The Bellman-Ford algorithm handles graphs with negative edge weights and detects negative cycles. Dijkstra's cannot manage negative weights, and Kruskal's or Prim's solve spanning tree problems, not shortest paths.
According to Cayley's formula, how many distinct spanning trees does the complete graph K_n have?
n^(n-2)
n!
n^(n-1)
2^(n-1)
Cayley's formula states that the complete graph on n vertices has n^(n-2) distinct spanning trees. The other expressions relate to different combinatorial counts and do not represent this specific value.
For a connected planar graph with V ≥ 3 vertices, what is the maximum number of edges E it can have according to Euler's inequality?
V + 1
2V - 4
V - 1
3V - 6
Euler's formula implies that a simple connected planar graph with V ≥ 3 satisfies E ≤ 3V - 6. The other formulas do not correctly bound the number of edges for planar graphs.
What is the maximum number of colors needed to color any planar graph so that no two adjacent vertices share the same color?
4
5
3
6
The four color theorem establishes that four colors suffice to color any planar graph without adjacent vertices sharing a color. While some specific planar graphs need fewer, no more than four are ever required.
In computational complexity theory, the graph isomorphism problem is known to be in which complexity class?
P
NP
co-NP
NP-complete
Graph isomorphism belongs to NP since a proposed vertex mapping can be verified in polynomial time. It is not known to be NP-complete or in P and is generally not classified as co-NP.
0
{"name":"In graph theory, what is a vertex?", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"In graph theory, what is a vertex?, What best describes an edge in a graph?, Which characteristic defines a directed graph?","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}

Learning Outcomes

  1. Identify key components such as vertices and edges
  2. Analyze different graph types like directed and undirected
  3. Evaluate connectivity and shortest path scenarios
  4. Apply traversal algorithms such as DFS and BFS
  5. Demonstrate understanding of trees, cycles, and planar graphs
  6. Master graph representation methods and isomorphism

Cheat Sheet

  1. Basic components of a graph - Every graph is built from vertices (the dots) and edges (the lines connecting them). Think of vertices as people at a party and edges as the friendships linking them. Understanding these building blocks is key to mapping any network.
  2. Directed vs. undirected graphs - In directed graphs, arrows show one-way relationships, like one-way streets in a city map. Undirected graphs treat connections as mutual, like handshakes between friends. Spotting the difference helps you choose the right tools for analysis.
  3. Graph connectivity - A graph is connected when you can travel from any vertex to any other via edges. It's like ensuring every island in an archipelago has a bridge to the mainland. Connectivity reveals the robustness and reachability in networks.
  4. Traversal algorithms (DFS & BFS) - Depth-First Search dives deep into one branch before backtracking, while Breadth-First Search fans out layer by layer. These techniques are your secret weapons for searching and discovering paths in labyrinthine graphs. Mastering them unlocks efficient pathfinding and exploration.
  5. Special graph structures - Trees are cycle-free connected graphs, cycles loop back to their start, and planar graphs can be drawn without crossing edges. Each structure has unique properties that simplify complex problems. Recognizing these patterns makes graph puzzles feel like playground games.
  6. Representation methods - Adjacency matrices use 2D arrays to flag edge presence, while adjacency lists keep tidy lists of neighbors. Matrices offer quick edge checks, lists save space for sparse graphs. Picking the right representation speeds up your algorithms.
  7. Graph isomorphism - Two graphs are isomorphic if you can relabel vertices of one to match the other perfectly. It's like spotting that two jigsaw puzzles are the same picture underneath different box art. Recognizing isomorphism helps identify equivalent structures in disguise.
  8. Eulerian & Hamiltonian paths - Eulerian paths traverse every edge exactly once, while Hamiltonian paths visit each vertex exactly once. These concepts solve real-world routing and scheduling puzzles, from street sweeping to sales routes. They're the blueprint for optimal tour designs.
  9. Vertex degree - The degree of a vertex counts how many edges touch it - like counting the number of friends someone has. In directed graphs, in-degree tallies incoming edges and out-degree tracks outgoing ones. Degrees help measure a node's influence and connectivity.
  10. Applications of graph theory - Graphs model everything from social networks and flight routes to molecule structures and computer networks. They turn complex systems into visual puzzles you can analyze and optimize. Embracing graph theory opens doors to countless real-world solutions.
Make a Quiz (FREE) Copy & Edit This Quiz Create a Quiz with AI

Education Quizzes

Powered by: Quiz Maker