34 Questions
In graph theory, what does a vertex represent?
Element in a graph
What do edges represent in a graph?
Links between vertices
Which of the following is a characteristic of an undirected graph?
Edges have orientation
What two components make up a graph in mathematical terms?
{Vertex set, Edge set}
In a regular graph, what does it mean if all vertices have the same degree?
All vertices are adjacent to each other
What happens if a cut-vertex is removed from a graph?
The graph becomes disconnected
What is the characteristic of a cycle graph in terms of vertex degrees?
Every vertex has degree 2
What property defines a regular graph?
All vertices have the same degree
How are complete graphs denoted?
$K_n$
What happens to a graph if a bridge (isthmus) is removed?
The graph becomes disconnected
What property defines a k-regular graph?
$k$ is the degree of all vertices
What is the significance of odd vertices in a graph according to the Handshaking Lemma corollary?
An odd number of vertices implies the graph is disconnected
In a cycle graph, what is the degree of each vertex?
2
How does a self-loop contribute to the degree of a vertex?
It contributes 2 to the degree
What is a simple graph?
A graph that contains no loops or parallel edges
In a bipartite graph, how are the vertices partitioned?
Into two disjoint subsets V1 and V2, where no edge joins vertices in the same subset
What is a complete bipartite graph denoted as?
$K_{r,s}$
What is a multigraph?
A graph that allows the existence of loops and parallel edges
What is the length of a walk in a graph?
The number of edges in the walk
When is a walk considered closed?
When it starts and ends at the same vertex
What is a semi-Eulerian graph defined as?
A graph that has an Euler trail
In a semi-Eulerian graph with two vertices of odd degree, where must an Euler trail start and end?
Start at one odd degree vertex, end at the other
Based on the information provided, why is a connected graph semi-Eulerian if it has 0 or 2 vertices of odd degree?
Because the remaining vertices have even degree
What is the defining feature of a non-Eulerian graph?
Having four or more vertices of odd degree
What condition must be satisfied for a connected graph to have an Euler circuit?
Every vertex must have an even degree
What is the defining characteristic of a Hamiltonian cycle on a graph?
It uses every vertex exactly once in a closed path
What distinguishes a semi-Hamiltonian graph from a Hamiltonian graph?
A semi-Hamiltonian graph does not form a closed path with every vertex visited once
Which type of graph is characterized by having a trail that passes through each vertex exactly once and doesn't form a closed path?
Semi-Hamiltonian Graph
Which of the following statements is true about a trail?
A trail is a walk where all edges are distinct, but vertices may be repeated.
Which of the following is a circuit?
1, 2, 3, 1, 5, 4, 3, 7, 1
What is the relationship between walks, trails, and paths in terms of set theory?
Paths ⊆ Trails ⊆ Walks
What condition must be satisfied for a connected graph to be Eulerian?
Every vertex of the graph must have an even degree.
Which of the following is an Euler trail?
An open trail that uses every edge of the graph exactly once.
According to the given information, which of the following graphs is Eulerian?
A graph where all vertices have even degrees.
Explore the basics of Graph Theory, including its applications in real-world scenarios like timetabling, internet representation, communication networks, and social networks. Learn how graphs are used to model various systems and structures.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
