Ch 9. Key Terms

Adjacent Vertices: Two vertices are adjacent if they are connected by an edge.

Bipartite Graph: A graph whose vertex set can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set.

Complete Bipartite Graph: A bipartite graph in which every vertex in the first set is connected to every vertex in the second set.

Complete Graph: A graph in which every pair of distinct vertices is connected by a unique edge.

Component: A maximal connected subgraph of a graph; no additional vertices or edges can be added without losing connectivity.

Connected Graph: An undirected graph in which there exists a path between every pair of distinct vertices.

Cycle: A path that starts and ends at the same vertex.

Degree of a Vertex: The number of edges incident to a vertex in an undirected graph.

Directed Acyclic Graph (DAG): A directed graph that contains no directed cycles.

Directed Euler Cycle: A cycle in a directed graph that uses every directed edge exactly once and respects edge directions.

Directed Graph (Digraph): A graph in which each edge has a direction, indicating a one‑way relationship between vertices.

Edge (Arc): A connection between two vertices in a graph.

Euler Cycle (Eulerian Circuit): A cycle that starts and ends at the same vertex and traverses every edge of an undirected graph exactly once.

Euler Trail (Euler Path): A path that traverses every edge of a graph exactly once but starts and ends at different vertices.

Incident: An edge is incident on a vertex if the vertex is one of the edge’s endpoints.

Indegree: The number of directed edges entering a vertex in a directed graph.

Isolated Vertex: A vertex with no incident edges.

Loop: An edge that connects a vertex to itself.

Outdegree: The number of directed edges leaving a vertex in a directed graph.

Parallel Edges: Two or more edges that connect the same pair of vertices.

Path: A sequence of vertices and edges where each edge connects consecutive vertices.

Simple Cycle: A cycle in which all vertices, except the starting and ending vertex, are distinct.

Simple Graph: A graph that contains no loops and no parallel edges.

Simple Path: A path in which all vertices and edges are distinct.

Subgraph: A graph formed from a subset of the vertices and a subset of the edges of a larger graph.

Vertex (Node): An object or entity represented as a point in a graph.

Weighted Graph: A graph in which each edge is assigned a numerical value (weight), representing cost, distance, or time.