Subgraphs¶

Induced Subgraph¶

An induced subgraph is a subgraph whose vertices form a subset of the original graph's vertices, and its edges include all edges between those vertices. An n-vertex graph has \(2^n\) induced subgraphs.

Spanning Subgraph¶

A spanning subgraph is a subgraph that includes all vertices of the original graph and any subset of its edges. An m-edge graph has \(2^m\) spanning subgraphs.

Some Notes¶

• The only spanning induced subgraph is the graph itself.

• The number of subgraphs of a graph depends on its structure.

Graph Partitioning¶

Graph partitioning refers to dividing a graph into several subgraphs such that: - Their edges do not overlap. - All edges of the original graph are covered.

In other words, every edge of the graph belongs to exactly one subgraph. You can think of partitioning as categorizing or edge-coloring. The figure below shows a partitioning of the graph \(K_4\) into two \(P_4\) graphs:

Independence Number and Clique Number¶

• The largest induced subgraph with no edges is called the maximum independent set. The number of vertices in this set is called the independence number of the graph, denoted by \(\alpha\) or \(\alpha(G)\) (the Greek letter "alpha").

• The largest induced subgraph where every pair of vertices is connected by an edge (i.e., a complete graph) is called the maximum clique. The number of vertices in this clique is called the clique number of the graph, denoted by \(\omega\) or \(\omega(G)\) (the Greek letter "omega").

These are important definitions, and many interesting problems revolve around them.