Graph Theory Definitions

These flashcards cover the definitions and key properties of graph theory concepts introduced in the lecture.

Graph

A set of vertices and edges connecting some pairs of vertices.

Vertex (node)

An individual object in a graph.

Edge

A connection between two vertices.

Degree

Number of edges incident to a vertex.

Regular Graph

A graph where every vertex has the same degree.

Adjacency List

A representation where each vertex stores a list of adjacent vertices.

Adjacency Matrix

A matrix where entry (i, j) indicates the presence (or absence) of an edge between vertices i and j.

Walk

A sequence of vertices and edges where each edge's endpoints are consecutive vertices.

Length of a Walk

Number of edges in the walk.

Closed Walk

A walk where the first and last vertices are the same.

Trail

A walk with no repeated edges.

Circuit

A closed trail (starts and ends at the same vertex without repeating edges).

Path

A walk with no repeated vertices.

Cycle

A closed path (starts and ends at the same vertex, no other repeated vertices).

Connected Graph

A graph in which there is a path between any two vertices.

Connected Component

A maximal set of connected vertices.

Edge Connectivity

The minimum number of edges that need to be removed to disconnect the graph.

k-Edge Connected Graph

A graph that remains connected whenever fewer than k edges are removed.

Euler Circuit

A closed walk that includes every edge exactly once.

Euler Trail

A walk that includes every edge exactly once but does not necessarily end at the starting vertex.

Even Degree

A vertex has even degree if the number of edges incident to it is even.

Hamiltonian Path

A path that visits every vertex exactly once.

Hamiltonian Cycle

A cycle that visits every vertex exactly once and returns to the starting vertex.

Isolated Vertex

A vertex with degree 0.

Maximal

A property is maximal if it cannot be extended by including one more element.

Incident

An edge is incident to a vertex if it is connected to that vertex.

Neighbors

Vertices connected by an edge.