Unit 4: Graph Theory-I - Subjective Questions

A graph is defined as an ordered pair where:

• is a non-empty set of vertices (also called nodes or points).
• is a set of edges (also called links or lines) that connect pairs of vertices.

Each edge is associated with either an ordered or unordered pair of vertices.

Basic components:

• Vertex (Node): A fundamental unit represented by a point.
• Edge: A connection between two vertices, represented as .
• Endpoints: The two vertices connected by an edge.
• Adjacent vertices: Two vertices joined by an edge.
• Incident edge: An edge is incident on its endpoints.

Example: Consider and . Here vertices and are adjacent, and edge is incident on and .

Simple Graph:

• A graph that contains no self-loops and no multiple (parallel) edges between the same pair of vertices.
• Between any two vertices, there exists at most one edge.
• Example: , forms a simple triangle graph.

Multigraph:

• A graph that allows multiple edges (parallel edges) between the same pair of vertices, but usually no self-loops.
• Example: Two vertices and connected by two distinct edges and .

Key Differences:

A pseudograph further allows self-loops in addition to multiple edges.

Degree of a Vertex:

The degree of a vertex , denoted , is the number of edges incident on it. A self-loop contributes 2 to the degree of a vertex.

For Undirected Graphs:

• number of edges touching .
• A vertex of degree is called an isolated vertex.
• A vertex of degree is called a pendant vertex.

For Directed Graphs:

• In-degree : The number of edges directed into vertex .
• Out-degree : The number of edges directed out of vertex .
• Total degree: .

Example: If vertex has 3 incoming and 2 outgoing edges, then , , and total degree .

Handshaking Theorem:

For any undirected graph , the sum of the degrees of all vertices is equal to twice the number of edges:

Proof:

• Consider each edge in the graph.
• Every edge has exactly two endpoints.
• When we count the degree of each vertex, each edge is counted twice — once for each of its two endpoints.
• Therefore, the total sum of all degrees equals times the number of edges.

Hence, .

Corollary (Handshaking Lemma):

In any undirected graph, the number of vertices with odd degree is always even.

Proof of Corollary: Split vertices into odd-degree set and even-degree set . Since is even, and the sum over is even, the sum over must also be even. A sum of odd numbers is even only if there is an even count of them.

Part 1: Number of edges

Using the Handshaking Theorem:

Sum of degrees .

Therefore:

The graph has 8 edges.

Part 2: Verification of degree sequence

Sum of degrees , which is even, so the Handshaking condition is satisfied ().

However, we must check feasibility: there are 4 vertices, so the maximum possible degree of any vertex is (in a simple graph). Since one vertex has degree , which is impossible in a simple graph with only 4 vertices, such a simple graph cannot exist.

Conclusion: The degree sequence is valid for a multigraph but not for a simple graph.

Subgraph:

A graph is a subgraph of if and , such that every edge in has both endpoints in .

Types of Subgraphs:

1. Spanning Subgraph:

• A subgraph that contains all the vertices of (i.e., ) but may have fewer edges.
• Used in finding spanning trees.
• Example: Removing some edges from while keeping all vertices.

2. Induced Subgraph:

• A subgraph obtained by selecting a subset of vertices and including all edges of whose both endpoints lie in .
• Denoted .
• Example: Choosing vertices and including every edge among them present in .

Key Difference: A spanning subgraph fixes the vertex set and varies edges; an induced subgraph fixes the vertex subset and takes all edges among them.

Isomorphic Graphs:

Two graphs and are said to be isomorphic if there exists a bijective function (one-to-one and onto) such that:

This means the adjacency relationship is preserved under the mapping. Isomorphic graphs are structurally identical and differ only in vertex labeling or drawing.

Necessary Conditions (Invariants):

• Both graphs must have the same number of vertices.
• Both graphs must have the same number of edges.
• Both must have the same degree sequence.
• The number of connected components must be equal.
• The number of cycles of each length must match.
• Both must have the same number of vertices of each degree.

Note: These conditions are necessary but not sufficient. Two graphs may satisfy all these conditions yet still not be isomorphic.

Step 1: Check number of vertices and edges.

• : 4 vertices, 4 edges.
• : 4 vertices, 4 edges. ✓

Step 2: Check degree sequences.

• In : . Sequence: .
• In : . Sequence: . ✓

Step 3: Structural analysis.

Both graphs are 4-cycles ():

• :
• :

Step 4: Define a bijection.

Map .

Check edges:

• ✓
• ✓
• ✓
• ✓

Conclusion: All edges are preserved. Therefore, and are isomorphic.

Homeomorphic Graphs:

Two graphs and are said to be homeomorphic if they can be obtained from the same graph by a sequence of edge subdivisions (or by smoothing out degree-2 vertices).

Elementary Subdivision: An edge is replaced by inserting a new vertex so that the edge becomes two edges and .

Two graphs are homeomorphic if their subdivisions produce isomorphic graphs.

Difference from Isomorphic Graphs:

Example: A triangle and a graph obtained by adding a vertex on one edge of the triangle (making it a path with 4 vertices forming a subdivided triangle) are homeomorphic but not isomorphic since they have different numbers of vertices.

Homeomorphic graphs are important in planarity testing (Kuratowski's theorem).

Walk:

A walk is a sequence of vertices and edges where each edge connects and . Vertices and edges may repeat.

Trail:

A trail is a walk in which no edge is repeated, but vertices may repeat.

Path:

A path is a walk in which no vertex is repeated (and consequently no edge is repeated). A path is the most restrictive.

Circuit (Closed Trail):

A circuit is a closed trail, i.e., a trail that begins and ends at the same vertex with no repeated edges.

Cycle (Closed Path): A closed path where no vertex repeats except the starting and ending vertex.

Summary Table:

Connectivity:

Connectivity describes whether it is possible to reach every vertex from every other vertex in a graph by traversing edges.

Connected Graph:

A graph is said to be connected if there exists a path between every pair of vertices. In other words, no vertex is isolated from the rest.

• Example: A triangle graph where every vertex is reachable from every other vertex.

Disconnected Graph:

A graph is disconnected if there exists at least one pair of vertices with no path between them. Such a graph consists of two or more separate pieces.

• Example: A graph with vertices where forms one component and forms another, with no edge connecting the two groups.

Connectivity in Directed Graphs:

• Strongly connected: There is a directed path between every pair of vertices in both directions.
• Weakly connected: The underlying undirected graph is connected.

Vertex Connectivity : The minimum number of vertices whose removal disconnects the graph.

Connected Component:

A connected component of a graph is a maximal connected subgraph of . This means:

• Every vertex within the component is reachable from every other vertex in that component.
• No vertex in the component is connected to any vertex outside the component.

A connected graph has exactly one connected component.

Determining the Number of Components:

• Use graph traversal algorithms like BFS (Breadth-First Search) or DFS (Depth-First Search).
• Start from an unvisited vertex, traverse all reachable vertices (marking them visited) — this forms one component.
• Repeat for the next unvisited vertex; each new traversal reveals a new component.
• The count of traversals equals the number of connected components.

Example:

Consider with edges .

• Component 1: (connected).
• Component 2: (connected).

Therefore, the graph has 2 connected components.

Distance:

The distance between two vertices and in a graph, denoted , is the length of the shortest path (minimum number of edges) between them. If no path exists, .

Properties:

• .
• (in undirected graphs).
• Satisfies triangle inequality: .

Diameter:

The diameter of a graph , denoted , is the maximum distance between any pair of vertices:

Calculation for :

The path graph : .

The distances:

• (maximum)

The maximum distance is between the two end vertices and .

Cut Vertex (Cut Point / Articulation Point):

A cut vertex is a vertex whose removal (along with its incident edges) increases the number of connected components of the graph, i.e., it disconnects the graph or a component.

• Example: In a path , vertex is a cut vertex because removing separates and .

Bridge (Cut Edge):

A bridge is an edge whose removal increases the number of connected components of the graph.

• Example: In the path , both edges and are bridges since removing any one disconnects the graph.

Significance:

• Network Reliability: Cut vertices and bridges represent weak points in networks. Their failure disconnects communication.
• Robustness Analysis: Networks with fewer cut points/bridges are more fault-tolerant.
• Bridge Property: An edge is a bridge if and only if it does not lie on any cycle.

Key Observation: A graph with no cut vertices is called a biconnected graph and is more resilient to failures.

1. Null Graph (Empty Graph):

• A graph with vertices but no edges. Denoted .
• Every vertex has degree (all isolated vertices).

2. Complete Graph ():

• A simple graph in which every pair of distinct vertices is connected by a unique edge.
• Number of edges: .
• Each vertex has degree .

3. Regular Graph:

• A graph in which every vertex has the same degree . Called a -regular graph.
• Example: A cycle graph is 2-regular.

4. Bipartite Graph:

• A graph whose vertices can be divided into two disjoint sets and such that every edge connects a vertex in to a vertex in .
• Contains no odd-length cycles.
• Complete bipartite graph denoted .

5. Weighted Graph:

• A graph in which each edge is assigned a numerical value (weight), representing cost, distance, or capacity.
• Used in shortest-path and minimum-spanning-tree problems.

Statement: In a complete graph with vertices, the number of edges is and each vertex has degree .

Proof of Degree:

• In , every vertex is connected to every other vertex exactly once.
• Since there are vertices total, each vertex is connected to the remaining vertices.
• Therefore, the degree of each vertex is:

Proof of Number of Edges:

Method 1 (Combinatorial):

An edge is formed by choosing 2 vertices out of . The number of ways to choose 2 vertices from is:

Method 2 (Using Handshaking Theorem):

Since every vertex has degree and there are vertices:

By the Handshaking Theorem, , so:

Hence proved.

Undirected Graph:

• Edges have no direction; an edge is the same as .
• Relationships are symmetric.
• Degree is a single value per vertex.

Directed Graph (Digraph):

• Edges have a direction; an edge points from to and differs from .
• Relationships may be asymmetric.
• Each vertex has an in-degree and an out-degree.

Comparison Table:

Representations:

• Adjacency Matrix: if edge exists. Symmetric for undirected graphs.
• Adjacency List: List of neighbors for each vertex.

Applications:

• Undirected: Social networks (friendships), road networks (two-way).
• Directed: Web page links, task scheduling, one-way streets, dependency graphs.

Adjacency Matrix:

For a graph with vertices, the adjacency matrix is an matrix where:

• For undirected graphs, is symmetric.
• The sum of a row (or column) gives the degree of that vertex.

Incidence Matrix:

For a graph with vertices and edges, the incidence matrix is an matrix where:

• Each column (representing an edge) contains exactly two 1's (its endpoints).

Adjacency Matrix for (triangle with vertices 1, 2, 3):

Edges: .

Each row sums to , confirming each vertex has degree .

Vertex Connectivity :

The vertex connectivity of a connected graph is the minimum number of vertices whose removal results in a disconnected graph or a trivial graph (single vertex).

• A graph is -connected if .

Edge Connectivity :

The edge connectivity of a connected graph is the minimum number of edges whose removal disconnects the graph.

• A graph is -edge-connected if .

Minimum Degree :

is the smallest degree among all vertices in .

Whitney's Inequality (Relationship):

Explanation:

• : Removing all edges incident to the minimum-degree vertex isolates it.
• : Vertex removal is at least as powerful as edge removal in disconnecting a graph.

Example: For a cycle : , , , satisfying the inequality with equality.

Isomorphism Invariants:

An invariant is a property preserved under graph isomorphism. If two graphs differ in any invariant, they are definitely not isomorphic. Common invariants include:

• Number of vertices
• Number of edges
• Degree sequence
• Number of connected components
• Number of cycles and their lengths
• Existence of subgraphs of certain types

Why Same Degree Sequence Does Not Guarantee Isomorphism:

The degree sequence is a necessary but not sufficient condition. Two graphs can have identical degree sequences yet different connectivity structures.

Illustrative Example:

Consider two graphs, each with 6 vertices, all of degree 2 (degree sequence ):

• Graph A: A single 6-cycle : .
• Graph B: Two disjoint triangles: , i.e., and .

Analysis:

• Both have 6 vertices, 6 edges, and identical degree sequences.
• However:
  • Graph A has 1 connected component; Graph B has 2 components.
  • Graph A has a cycle of length 6; Graph B has cycles of length 3 only.

Conclusion: Since the number of connected components and cycle structure differ, the two graphs are not isomorphic, despite matching degree sequences. This demonstrates why matching invariants alone cannot confirm isomorphism.