Graph classes

We now go through basic terminologies in graph theory. Graph $H$ is a subgraph of $G$ if $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$. Further, a subgraph $H$ of $G$ is said to be a spanning subgraph if $V(H) = V(G)$. Let $G$ be a graph and $S \subseteq V(G)$, the induced subgraph of $G$ on vertex set $S$, denoted by $H=G[S]$, has vertex set $V(H) = S$ and edge set $E(H) = \{\{u,v\} \in (S \times S) \cap E(G)\}$. In words, an induced subgraph on $S$ is obtained from $G$ by deleting vertices outside of $S$ as well as all edges incident to such vertices. We now list some important classes of graphs.

• Complete graphs: For any $n \in {\mathbb N}$, the graph $K_n$ is a complete graph on $n$ vertices and edge set $E(K_n) = \{\{u,v\}: u\neq v \in V\}$, i.e., there is an edge between every pair of distinct vertices. A complete graph is also called a clique.

• Bipartite graphs: A graph $G$ is bipartite if $V(G) = A \cup B$, with $A \cap B = \emptyset$, such that $E(G) \subseteq A \times B$. The complete bipartite graph (a.k.a. biclique), denoted by $K_{m,n}$, has $|A| = m$, $|B|=n$, and there is an edge connecting every pair $\{u,v\} \in A \times B$.

• Paths: A path is a walk that does not repeat any vertex. For any $n \in {\mathbb N}$, the graph $P_n$ is a path on $n$ vertices, i.e. $V(P_n)= \{v_1,\ldots, v_n\}$, and $\{v_i, v_{i+1}\} \in E(P_n)$ for all $i= 1,\ldots, n-1$.

• Cycles: A cycle is a closed walk that does not repeat any vertex (except for the first equal to the last). For any $n\in {\mathbb N}$, the graph $C_n$ is a cycle on $n$ 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 $G$ be a bipartite graph with vertex partition $V(G) = L \cup R$.

1. Prove that $\sum_{v \in L} \deg(v) = \sum_{v \in R} \deg(v)$

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.