Bipartite Graphs and Subgraphs

Bipartite Graphs

• A Bipartite graph is a graph that can be divided into two distinct sets (V1 and V2) of vertices such that every edge connects a vertex in V1 to a vertex in V2, never connecting two vertices in the same set.
• A simple graph is bipartite if and only if its vertices can be colored with two distinct colors without any adjacent vertices having the same color.

Complete Bipartite Graphs

• A complete bipartite graph Km,n has two sets of vertices, one with 'm' vertices and the other with 'n' vertices.
• Every vertex in the first set is connected to every vertex in the second set, resulting in a complete bipartite graph.

Subgraphs

• A subgraph of a graph G is a graph H whose vertices and edges are a subset of G.
• An induced subgraph is created by selecting a set of vertices from the original graph and including all edges that connect those vertices in the original graph.
• Removing a vertex 'v' and all its incident edges from a graph G produces a subgraph denoted by G - v.

Union of two Graphs

• The union of two graphs, G1 and G2, is a new graph with the combined vertex set of both graphs and their combined edge sets.
• The complement of a graph G has the same vertices as G, but two vertices are adjacent in the complement only if they are not adjacent in the original graph.

Graph Isomorphism

• Two graphs are considered isomorphic if they have the same structure, even if their vertex labels or edge arrangement are different.
• An isomorphism between two graphs is a one-to-one correspondence between the vertices of the two graphs that preserves adjacency relationships.
• Key features for two graphs to be isomorphic:
  • They must have the same number of vertices.
  • They must have the same number of edges.
  • The degrees of corresponding vertices in both graphs must be the same.

Graphic Sequence

• The degree sequence of a graph is the list of degrees of all vertices, usually written in non-increasing order.
• A graphic sequence is a sequence that can be the degree sequence of a simple graph.
• Not all sequences are graphic, and the Havel-Hakimi Theorem can be used to determine if a sequence is graphic.
• In a simple graph with at least two vertices, there must be at least two vertices with the same degree.
• Regular graphs are graphs where all vertices have the same degree, and an n-regular graph has a degree of n for every vertex.
• Examples of regular graphs are Kn, Cn, Wn, and Qn for specific values of 'n'.

Paths and Related Terminology

• A walk in a graph is an alternating sequence of vertices and edges, starting and ending with vertices.
• A closed walk is a walk that starts and ends at the same vertex.
• A trail is a walk with no repeated edges.
• A closed trail is called a circuit.
• A path is a trail with no repeated vertices.

Connected Graph

• An undirected graph is called connected if there is a path between every pair of distinct vertices.
• A disconnected graph is a graph that is not connected.
• Every pair of distinct vertices in a connected graph has a simple path between them.

Components of a Graph

• A connected component of a graph is a subgraph that is connected and not a proper subgraph of another connected subgraph.
• A connected component of a graph is a maximal connected subgraph, meaning it cannot be expanded further.

Cut vertex and Cut edge

• A cut vertex (or articulation point) is a vertex whose removal increases the number of connected components in a graph.
• A cut edge (or bridge) is an edge whose removal increases the number of connected components in a graph.
• If a graph has more than two vertices, at least one endpoint of a bridge is a cut vertex.

Nonseparable Graphs

• A connected graph without a cut vertex is called a nonseparable graph.
• The complete graph Kn, where n ≥ 3, has no cut vertices.
• Connectivity in graphs refers to the number of vertices or edges needed to be removed to disconnect the graph.
• A vertex cut (or separating set) is a subset of vertices whose removal disconnects the graph.
• The vertex connectivity of a graph is the minimum number of vertices in a vertex cut.

k-connected graph

• A graph is k-connected if it cannot be disconnected by removing fewer than 'k' vertices.
• A graph is 1-connected if it is connected and not a single vertex graph.
• A graph is 2-connected or biconnected if it is nonseparable and has at least three vertices.

Edge Connectivity

• The edge connectivity of a graph is the minimum number of edges that need to be removed to disconnect the graph.
• The edge connectivity of a graph is always less than or equal to the minimum degree of the graph.

Connectedness in Directed Graphs

• A directed graph is strongly connected if there is a path from any vertex to any other vertex in the graph, going in either direction.
• A directed graph is weakly connected if the underlying undirected graph (ignoring directions) is connected.

This quiz explores the concepts of bipartite graphs, complete bipartite graphs, and subgraphs. You'll learn about the distinct sets of vertices in bipartite graphs and how to identify and create subgraphs. Test your understanding of these fundamental graph theory topics.