Scribd
Upload
3 views3 pages

Graph Theory Concepts and Definitions

The document provides definitions and examples related to graph theory, including concepts such as graphs, vertices, connected and disconnected graphs, cut vertices, bridges, and connectivity measures. It also discusses matching, perfect matching, vertex and edge colouring, along with their respective chromatic numbers and indices. These foundational concepts are essential for understanding the structure and properties of graphs.

Uploaded by

Shanawaz Mansoori
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Graph Theory Concepts and Definitions

The document provides definitions and examples related to graph theory, including concepts such as graphs, vertices, connected and disconnected graphs, cut vertices, bridges, and connectivity measures. It also discusses matching, perfect matching, vertex and edge colouring, along with their respective chromatic numbers and indices. These foundational concepts are essential for understanding the structure and properties of graphs.

Uploaded by

Shanawaz Mansoori
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Graph Theory Lecture Notes

Definition: Graph

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices.

Example:

V = {A, B, C, D}, E = {(A,B), (B,C), (C,D)} forms a simple path graph.

Definition: Vertex

A vertex is a fundamental unit of a graph representing a point or node.

Example:

In graph G with V = {1,2,3}, each number is a vertex.

Connected Graph

A graph is connected if a path exists between every pair of vertices.

Example:

Edges {(A,B),(B,C),(C,D)} form a connected graph.

Disconnected Graph

A graph that has two or more components.

Example:

Edges {(A,B)} and {(C,D)} form two disconnected components.

Cut Vertex

A vertex whose removal increases the number of components.

Example:

In A–B–C–D, removing B disconnects the graph.

Bridge (Cut Edge)

An edge whose removal increases the number of components.


Example:

In A–B–C–D, removing (B,C) disconnects the graph.

Vertex Connectivity k(G)

Minimum number of vertices whose removal disconnects G.

Example:

k(K3)=2.

Edge Connectivity λ(G)

Minimum number of edges whose removal disconnects G.

Example:

λ(K3)=2.

Matching

A set of edges with no shared vertices.

Example:

In path A–B–C–D, {(A,B),(C,D)} is a matching.

Perfect Matching

A matching covering all vertices.

Example:

Square A–B–C–D–A, perfect matching: {(A,B),(C,D)}.

Vertex Colouring

Assigning colours to vertices so adjacent vertices differ.

Example:

Triangle K3 needs 3 colours.

Chromatic Number χ(G)

Minimum colours needed in vertex colouring.


Example:

χ(C4)=2, χ(K4)=4.

Edge Colouring

Colouring edges so adjacent edges differ.

Example:

K3 needs 3 edge colours.

Chromatic Index χ'(G)

Minimum colours required for edge colouring.

Example:

χ'(K3)=3.

You might also like