8.1 Some Definitions

• G = (V, E)

  Each edge is an unordered pair of vertices

• v and w are adjacent if (v, w) or equivalently (w, v) is an edge. The edge (v, w) is incident upon the vertices v and w.
• A path is a sequence of vertices v₁, v₂,..., v_n, such that (v_i, v_{i + 1}) is an edge for 1 $\leq$ i < n. A path is simple if all vertices on it are distinct, except possibly v₁ and v_n. The path has length n - 1 and connects v₁ and v_n.
• A graph is connected if every pair of vertices is connected.
• A subgraph G' = (V', E') of a graph G = (V, E) is a graph such that

  1.

  V' $\subseteq$ V

  2.

  E' contains some edges (u, v) of E such that both u and vare in V'

  If E' contains all edges (u, v) $\in$ E for which u, v $\in$ V', the subgraph G' is called an induced subgraph.

• A connected component of a graph is an induced subgraph which is connected and which is not a proper subgraph of any other connected subgraph of G (i.e., maximal connected induced subgraph).
• A simple cycle is a simple path of length $\geq$ 3, that connects a vertex to itself.
• A graph is cyclic if it contains at least one (simple) cycle.
• A free tree is a connected, acyclic graph.

  
  

    

  Figure 8.1: Examples of undirected graphs

  
  
  

• Observe that

  1.

  Every free tree with n vertices contains exactly n - 1 edges

  2.

  If we add any edge to a free tree, we get a cycle.

• See Figure 8.1 for several examples.