Flashcards on Basics of Graph Theory



What is a graph in graph theory?

A graph is a collection of vertices (or nodes) and edges that connect pairs of vertices.

What are vertices in a graph?

Vertices, also called nodes, are points in a graph where edges meet.

What are edges in a graph?

Edges are the connections between pairs of vertices in a graph.

What is a directed graph?

A directed graph is a graph in which the edges have a direction, indicated by an arrow.

What is an undirected graph?

An undirected graph is a graph in which the edges have no direction.

What is a weighted graph?

A weighted graph is a graph in which each edge is assigned a weight or cost.

What is a simple graph?

A simple graph is a graph without loops and multiple edges between any two vertices.

What is a complete graph?

A complete graph is a graph in which every pair of vertices is connected by an edge.

What is a path in graph theory?

A path is a sequence of edges that connect a sequence of distinct vertices.

What is a cycle?

A cycle is a path that starts and ends at the same vertex, with all other vertices distinct.

What is a connected graph?

A connected graph is a graph in which there is a path between every pair of vertices.

Define a subgraph.

A subgraph is a graph formed from a subset of the vertices and edges of another graph.

What is a degree of a vertex?

The degree of a vertex is the number of edges incident to it.

What is a bipartite graph?

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.

What is a tree in graph theory?

A tree is a connected graph with no cycles.