Graph

Let $V$ be a finite nonempty set of nodes.

Let $E \subseteq V \times V$ be a set of edges.

$G = (V, E)$ is the directed graph (or digragh) made up of the node set $V$ and the edge set $E$.

• $G_1 = (V_1, E_1)$ is called a subgraph of $G$ if
  • $\empty \neq V_1 \subseteq V$
  • $E_1 \subseteq V_1 \times V_1$
  • $E_1 \subseteq E$
• $G_1$ is an induced subgraph of $G$ if it is a subgraph of $G$ and $E_1 = E \cap (V_1 \times V_1)$
• A component is a maximal subgraph that is connected.

When $E$ is considered to consist of unordered pairs, $(V, E)$ is called an undirected graph.

• An undirected graph $G$ is connected if there is a path between any two distinct nodes of $G$

A graph is loop-free if it contains no (self-)loops.

A multigraph allows parallel edges between nodes.

A loop-free undirected graph without parallel edges between nodes is said to be simple.

A node is isolated if it has no incident edges.

For an undirected graph, we typically use $\{x, y\}$ to represent a edge; as for digraph, we always use $(x, y)$ to represent an edge.

All kinds of Walks on Undirected Graphs

A walk from $x$ to $y$ is a finite sequence of non-loop edges connecting $x$ and $y$.

The length of a walk is the number of edges in it.

• A walk from $x$ to $y$ where $x \neq y$ is called an open walk.
• A walk from $x$ to itself is called a closed walk.
• A walk without repeated edges is called a trail.
  • A closed trail is called a circuit.