Graph classes

We now go through basic terminologies in graph theory. Graph is a subgraph of if and . Further, a subgraph of is said to be a spanning subgraph if . Let be a graph and , the induced subgraph of on vertex set , denoted by , has vertex set and edge set . In words, an induced subgraph on is obtained from by deleting vertices outside of as well as all edges incident to such vertices. We now list some important classes of graphs.

• Complete graphs: For any , the graph is a complete graph on vertices and edge set , i.e., there is an edge between every pair of distinct vertices. A complete graph is also called a clique.

• Bipartite graphs: A graph is bipartite if , with , such that . The complete bipartite graph (a.k.a. biclique), denoted by , has , , and there is an edge connecting every pair .

• Paths: A path is a walk that does not repeat any vertex. For any , the graph is a path on vertices, i.e. , and for all .

• Cycles: A cycle is a closed walk that does not repeat any vertex (except for the first equal to the last). For any , the graph is a cycle on vertices.

• Trees: A tree is a connected graph without a cycle.

• Forests: A forest is a graph without a cycle. In particular, each connected component of a forest is a tree.

Exercise 15

Let be a bipartite graph with vertex partition .

1. Prove that

2. Prove that a graph is bipartite if and only if its vertices can be colored by red and blue so that neighboring vertices do not receive the same color.