Subgraphs
===============

A subgraph of a graph consists of a subset of vertices and a subset of edges between those vertices.

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 :math:`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 :math:`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 :math:`K_4` into two :math:`P_4` graphs:

.. figure:: /_static/dot/K_4_to_P_4.svg
 :width: 30%
 :align: center
 :alt: افراز گراف k4 به p4


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 :math:`\alpha` or :math:`\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 :math:`\omega` or :math:`\omega(G)` (the Greek letter "omega").

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