Discrete Mathematics - Graph Theory

These flashcards cover essential vocabulary and concepts related to Graph Theory in Discrete Mathematics, facilitating study and review for the exam.

Graph

An algebraic structure comprised of two sets: a set of vertices (V) and a set of edges (E) connecting the vertices.

Vertex

A node in a graph, represented as an element in set V.

Edge

A link connecting a pair of vertices in a graph, represented as an element in set E.

Adjacency

Two vertices are adjacent if they are the endpoints of a valid edge.

Incidence

An edge is said to be incident to a vertex if the vertex is one of its endpoints.

Degree

The number of incident edges to a vertex.

Disconnected Graph

A graph that comprises several isolated connected graphs, each called a component.

Euler Line

A walk that traverses through all the edges of a graph visiting them exactly once.

Hamiltonian Path

A walk in which every vertex is visited exactly once.

Complete Graph

A graph with maximal connectivity; every pair of distinct vertices is connected by a unique edge.

Chromatic Number (χ)

The minimum number of different colors needed to color a graph's vertices such that no two adjacent vertices share the same color.

Isomorphism

A relationship where two graphs are said to be isomorphic if they have a one-to-one correspondence between their vertices, edges, and adjacencies.

Subgraph

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