Study Notes for Graph Theory (GAMAT401)

GAMAT401: GRAPH THEORY

MODULE-I: INTRODUCTION TO GRAPHS

1. Introduction

Basic definitions
Applications of graphs
Types of graphs
    - Finite graphs
    - Infinite graphs
    - Bipartite graphs

2. Core Concepts

2.1 Definition of a Graph

A graph is defined as a pair $G = (V, E)$ where:
- V: A non-empty set containing vertices (nodes).
- E: A set containing edges which can be represented as unordered pairs of vertices.
Example:
- If $V = {V_1, V_2, V_3, V_4, V_5, V_6}$
- And $E = {e_1, e_2, …, e_{10}}$ with 6 vertices and 10 edges.

2.2 Edge Representation

Each edge in $E$ can be represented by an unordered pair of vertices, known as the end vertices of that edge.

3. Types of Edges

3.1 Self Loop

A self loop is an edge $e$ where both ends are the same vertex.
Example: If $V_2$ has a self loop $e_2$ then $e_2$ connects $V_2$ to itself.

3.2 Parallel Edges

Two edges are parallel if they share the same end vertices.

3.3 Simple Graph

A simple graph is one that does not contain self loops and has no parallel edges.

3.4 General Graph or Multigraph

A graph that can include self loops or parallel edges is referred to as a general graph or multigraph.

3.5 Isolated Vertex

A vertex is isolated if it is not an end vertex of any edge in the graph.

4. Finite & Infinite Graphs

Finite Graph: Contains a finite number of vertices and edges.
Infinite Graph: Contains an infinite number of vertices and/or edges.

5. Incidence & Degree

5.1 Incidence

An edge is said to be incident with its end vertices. If edge $e$ is incident with vertices $V_1$ and $V_2$ , this is described as the edge being between these two vertices.

5.2 Degree (Valency)

The degree of a vertex $V$ , denoted by $d(V)$ , is the number of edges incident to it. Self loops count twice.
  - Example:
    - $d(V_1) = 3$ : Vertex $V_1$ has 3 edges.
    - $d(V_2) = 4, d(V_3) = 2, d(V_4) = 1$

5.3 Pendant Vertex

A pendant (or end) vertex is a vertex of degree 1.
An isolated vertex is different; it has degree 0 ( $d(V) = 0$ ).

6. Regular Graph

A graph where all vertices have the same degree is called a regular graph.
A $k$ -regular graph means every vertex has degree $k$ .

7. Null Graph / Empty Graph / Trivial Graph

A null graph is a graph with no edges; the edge set is empty while the vertex set remains non-empty, leading to all vertices being isolated.

8. Theorems in Graph Theory

8.1 Theorem I: Sum of Degrees

The first theorem states that the sum of the degrees of all vertices in a graph $(G)$ is equal to twice the number of edges:
- $\sum d(V_i) = 2e$
- Because each edge contributes to the degree of two vertices.

8.2 Even and Odd Vertices

If a vertex has an even degree, it is called an even vertex. If it has an odd degree, it is known as an odd vertex.
The number of vertices with odd degree in a graph is always even.

9. Applications of Graph Theory

Graph theory has applications in various fields including:
  - Engineering
  - Physical and biological sciences
  - Linguistics and network designs.

10. Examples of Applications

Example 1: Konigsberg Bridge Problem

The problem involves whether one can cross each of seven bridges connecting two islands without swimming through the river or crossing the bridges more than once. Euler proved that such a solution does not exist.

Example 2: Utilities Problem

The problem involves connecting three houses to three utilities (water, gas, electricity) without any conduits crossing. It has been shown that such a connection cannot be achieved in a planar form.

Example 3: Electrical Network Problem

Involves the connection of electrical elements represented as vertices and edges of the graph, demonstrating different network topologies.

Example 4: Seating Problem

Involves arranging seating at tables for a fixed number of members such that every member sits next to different neighbors over multiple instances.

11. Complete Graph

A complete graph contains an edge between every pair of vertices. A complete graph with $n$ vertices is denoted as $K_n$ .

12. Bipartite Graph

A bipartite graph is 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.
- Example:
- Let $X = {V_1, V_2, V_3}$ and $Y = {V_4, V_5}$ .

13. Graph Isomorphism

Two graphs are isomorphic if there is a one-to-one correspondence between their vertices and edges that preserves incidence relationships.
Basic requirements include:
  - Same number of vertices.
  - Same number of edges.
  - Same degree sequences.

14. Connected and Disconnected Graphs

14.1 Definition of Connected Graph

A graph is connected if there is at least one path between every pair of vertices.

14.2 Components of a Graph

A disconnected graph consists of two or more connected subgraphs. Each of these subgraphs is referred to as a component.

15. Subgraphs

A subgraph $H$ of graph $G$ is a graph formed from a subset of vertices and edges of $G$ .
Edge-disjoint Subgraphs: Two subgraphs are edge-disjoint if they share no edges.

16. Walks, Paths, and Circuits

16.1 Walk

A walk is a finite alternating sequence of vertices and edges of a graph. A walk that begins and ends at the same vertex is called a closed walk.

16.2 Trail

A trail is a walk in which no edges are repeated.

16.3 Path

A path is an open walk in which no vertices occur more than once.
The length of a path is defined by the number of edges in it.

16.4 Circuit

A circuit (cycle) is a closed path.

17. Further Theorems

The degree properties state that in any graph, the sum of the degrees of all vertices must be even. This ties back to the concept of odd and even degrees of vertices found within the connectedness of a graph.

18. Problems and Exercises

Problems provided aim to strengthen understanding of topics such as degrees of vertices, types of graphs, and the application of theorems within graph theory.

Conclusion

Graph theory encompasses various complex structures and relationships that can be modeled mathematically, showcasing its broad application in several fields.