Lecture 13 - Notes

February 22, 2016

Undirected Graphs

We can consider a graph,

$$\begin{align} G = (V,E) \end{align}$$

Bipartite Graph

definition: A graph is bipartite is there is a partition $A,B$ of $V$ such that all edges $(a,b) \in E$ have $a \in A$ and $b \in B$.

Trees are an example of a bipartite set, we can show this using a two coloring. So are paths, even cycles, and complete bipartite graphs.

Subgraphs

definition: A graph $G^\prime$ is a subgraph of a graph $G$ if $V^\prime \subseteq V$, $E^\prime \subseteq E$ and all edges in $E^\prime$ are valid.

There are a few special types of subgraphs,

• spanning: Uses all the vertices in $G$, i.e., $V^\prime = V$
• induced: Uses all the valid edges in $G$ (with the selected vertices)