Unit4 - Subjective Questions

Statement:
In any undirected graph , the sum of the degrees of all vertices is equal to twice the number of edges. Mathematically:

Proof:

1. Let be an undirected graph where is the set of vertices and is the set of edges.
2. By definition, the degree of a vertex , denoted as , is the number of edges incident to it.
3. Consider an edge connecting vertices and .
4. When we count the degrees of all vertices, this edge contributes 1 to the degree of and 1 to the degree of .
5. Therefore, every edge contributes exactly 2 to the total sum of degrees.
6. Since there are edges in total, the sum of degrees is .

Corollary: The number of vertices of odd degree in a graph is always even.

1. Complete Graph ():
A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. It is denoted by , where is the number of vertices.

2. Cycle Graph ():
A cycle graph (for ) consists of vertices and edges . It forms a closed loop.

Number of edges in :
Since every vertex is connected to every other vertex:

• Each of the vertices has a degree of .
• Using the Handshaking Theorem: .
• Therefore, .

Definition:
Two graphs and are isomorphic if there exists a one-to-one correspondence (bijection) function such that for any two vertices , the edge exists in if and only if the edge exists in . In simpler terms, the graphs have the same structure but differ only in the labels of their vertices.

Necessary Conditions (Invariants):
For and to be isomorphic, they must have:

1. The same number of vertices ().
2. The same number of edges ().
3. The same degree sequence (the list of vertex degrees sorted in non-increasing order must be identical).
4. If one graph has a cycle of length , the other must also have a cycle of length .

Note: These conditions are necessary but not sufficient.

1. Adjacency Matrix:

• Definition: A square matrix of size (where is the number of vertices).
• Entry: if there is an edge between vertex and ; otherwise $0$ (for simple unweighted graphs).
• Properties: It is symmetric for undirected graphs. The diagonal elements are $0$ unless there are self-loops.
• Space Complexity: .

2. Incidence Matrix:

• Definition: A matrix of size (where is vertices, is edges).
• Entry: if vertex is incident to edge ; otherwise $0$.
• Properties: Each column (representing an edge) has exactly two $1$s (for undirected graphs without self-loops).
• Space Complexity: .

Comparison:
Adjacency matrices relate vertices to vertices, while incidence matrices relate vertices to edges.

Objective: To find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights.

Algorithm Steps:

1. Initialization:

   • Set distance to source .
   • Set distance to all other vertices .
   • Create a set of all unvisited vertices.

2. Iterative Process:

   • While is not empty:
     • Select the vertex in with the minimum .
     • Remove from (mark as visited).
     • Relaxation: For each neighbor of still in :
       • Calculate alternative distance: .
       • If , update and record as the predecessor of .

3. Termination: The algorithm stops when the destination is reached or is empty. The array holds the shortest distances.

Bipartite Graph:
A simple graph is bipartite if its vertex set can be partitioned into two disjoint sets and () such that every edge in the graph connects a vertex in and a vertex in . No edge connects two vertices within the same set.

Determination (Test):
A graph is bipartite if and only if it satisfies one of these equivalent conditions:

• It is 2-colorable: Vertices can be colored with two colors such that no two adjacent vertices have the same color.
• It contains no odd cycles: Every cycle in the graph has an even length.

Complete Bipartite Graph ():
A bipartite graph where every vertex in set (size ) is connected to every vertex in set (size ). The number of edges is .

1. Regular Graph:
A graph where every vertex has the same degree is called a -regular graph.

• Example: A triangle () is 2-regular.

2. Wheel Graph ():
Formed by taking a cycle graph () and adding a single new vertex (the "hub") connected to all vertices of the cycle.

• Vertices:
• Edges:

3. Cube Graph ():
Also known as an -cube or hypercube. It has vertices representing bit strings of length . Two vertices are adjacent if their bit strings differ by exactly one bit.

• Vertices:
• Edges:
• Example: is a standard cube.

Directed Graph Connectivity:

1. Strongly Connected:
A directed graph is strongly connected if for every pair of vertices , there is a directed path from to AND a directed path from to .

• Essentially, you can reach any vertex from any other vertex following the direction of the edges.

2. Weakly Connected:
A directed graph is weakly connected if replacing all directed edges with undirected edges results in a connected undirected graph.

• This means there is a "path" between any two vertices if we ignore edge directions, but not necessarily when respecting directions.

Summary:

• Strong connectivity implies weak connectivity, but not vice-versa.

1. Walk:
A finite sequence of alternating vertices and edges . In a simple graph, it is often denoted just by vertices . Vertices and edges can be repeated.

2. Trail:
A walk in which no edges are repeated. Vertices may be repeated.

3. Path (Simple Path):
A walk in which no vertices are repeated (consequently, no edges are repeated either).

4. Cycle (Circuit):
A closed path of length at least 3. It starts and ends at the same vertex (), and no other vertices are repeated.

1. Interpreting the Matrix:

• Row/Col 1 (a): Connected to b (2nd) and c (3rd).
• Row/Col 2 (b): Connected to a (1st) and d (4th).
• Row/Col 3 (c): Connected to a (1st) and d (4th).
• Row/Col 4 (d): Connected to b (2nd) and c (3rd).

2. Drawing the Graph:

• Vertices: .
• Edges: .
• Visual: This graph looks like a square or cycle ().

3. Calculating Degrees:

• : Connections to b, c 2
• : Connections to a, d 2
• : Connections to a, d 2
• : Connections to b, c 2

The graph is a 2-regular graph.

1. Cut Vertex (Articulation Point):
A vertex in a connected graph is a cut vertex if its removal (along with incident edges) disconnects the graph (i.e., increases the number of connected components).

2. Cut Edge (Bridge):
An edge in a graph is a bridge if its removal disconnects the graph.

Example:
Consider a graph: .

• Cut Vertex: Vertex . If we remove , and become isolated and disconnected.
• Cut Edges: Edge and Edge . Removing either one separates a vertex from the rest.
• Counter-Example: In a triangle (), there are no cut vertices or bridges because alternative paths exist.

Theorem:
In a directed graph (digraph) , the sum of the in-degrees of all vertices is equal to the sum of the out-degrees of all vertices, and both are equal to the total number of edges.

Mathematical Statement:

Explanation:

• (In-degree): Number of edges pointing to vertex .
• (Out-degree): Number of edges pointing from vertex .
• Every directed edge starts at (contributing 1 to 's out-degree) and ends at (contributing 1 to 's in-degree).
• Therefore, counting total in-degrees counts every edge once, and counting total out-degrees counts every edge once.

Adjacency Matrix Structure:
If the vertices of a bipartite graph are ordered such that all vertices in set come first, followed by vertices in , the adjacency matrix takes the form of a block matrix:

• The $0$ blocks on the diagonal indicate no edges within or within .
• represents the connections between and .

Spectrum (Eigenvalues):
The spectrum of a bipartite graph is symmetric with respect to 0. This means if is an eigenvalue of the adjacency matrix, then is also an eigenvalue.

Reasoning:

1. Definition of Bipartite: A graph is bipartite if it contains no odd cycles (cycles of odd length). Alternatively, vertices can be split into two sets with no internal connections.
2. Case (): Single vertex. No edges. Trivially bipartite.
3. Case (): Two vertices connected by an edge. . Bipartite.
4. Case (): A triangle. It is a cycle of length 3 (Odd). Therefore, not bipartite.
5. Case : Any with contains as a subgraph (any 3 vertices form a triangle). Since it contains an odd cycle (), it cannot be bipartite.

Conclusion:
is bipartite only for and .

Graph: Vertices . Source: .

Step-by-Step Execution:

1. Init: , others . Unvisited: .
2. Visit A: Neighbors .
   • Done with A.
3. Select min unvisited: (dist 2).
   • Neighbors of C: .
   • Path to B via C: . Since , update . (Predecessor )
   • Path to D via C: . Update .
   • Path to E via C: . Update .
   • Done with C.
4. Select min unvisited: (dist 3).
   • Neighbors of B: .
   • Path to D via B: . Since , update . (Predecessor )
   • Done with B.
5. Select min unvisited: (dist 8).
   • Neighbors of D: .
   • Path to E via D: . Since , update . (Predecessor )
6. Select E: Target reached.

Result: Shortest distance is 10. Path: .

1. Subgraph:
A graph is a subgraph of if:

• (Vertices of H are a subset of V)
• (Edges of H are a subset of E)
• Endpoints of edges in must be in .

2. Induced Subgraph:
An induced subgraph is a specific type of subgraph obtained by selecting a subset of vertices and keeping all edges from the original graph that connect pairs of vertices in .

• Notation: or .
• Condition: For any , if edge , then must be in .

Difference: In a standard subgraph, you can remove edges between kept vertices. In an induced subgraph, you cannot remove edges if the vertices remain.

1. Isolated Vertex:

• Definition: A vertex that is not connected to any other vertex in the graph.
• Degree: .
• Visual: A point floating alone.

2. Pendant Vertex (Leaf):

• Definition: A vertex that is connected to exactly one other vertex.
• Degree: .
• Visual: The endpoint of a line segment or the tip of a branch in a tree.

1. Adjacency Matrix:

• Pros:
  • Checking if edge exists is .
  • Simple to implement.
  • Good for dense graphs.
• Cons:
  • Space complexity is , wasteful for sparse graphs.
  • Iterating over neighbors takes .

2. Adjacency List:

• Pros:
  • Space complexity is , efficient for sparse graphs.
  • Iterating over neighbors is proportional to the degree of the vertex.
• Cons:
  • Checking if edge exists takes (not constant time).
  • Slightly more complex to implement compared to a matrix.

1. 3-Cube ():

• Vertices (): where . .
• Edges (): . .

2. Complete Bipartite ():

• Here and .
• Vertices (): .
• Edges (): .

Answer: No.

Reason 1: Simple Graph Constraint

• In a simple graph with vertices, the maximum possible degree of a vertex is (it can connect to all other vertices but not itself).
• Here, . The maximum degree should be $4$.
• The sequence contains a degree of 5. A vertex cannot be connected to 5 distinct vertices in a graph with only 5 vertices total (unless multigraphs/loops allowed, but the question specifies "simple graph").

Reason 2: Handshaking Theorem

• Sum of degrees = .
• The Handshaking Theorem states . The sum must be an even number.
• 15 is odd. Therefore, no such graph exists.