Introduction

$G=(V,E)$, pair of vertex and edges

$V = {v1, v2, v3, v4, v5}$

$E = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v3, v5), (v4, v5)}$

• Walk: sequence of vertex by following edges
• Path: special walk with no repeating vertex
• Type:
  • directed & undirected - edges with direction
  • cyclic & acyclic - cycle or not
  • weighted & unweighted - edges with weight

Undirected graph

ignore the arrows above

• degree (v6) - 2
• Sum of degrees = 2 * |E|
• Max no of edges = (|v| * (|V| - 1)) // 2
• (Eg) Walk : v1 -> v2 -> v4 -> v2
• (Eg) Path: v1 -> v2 -> v4

Directed graph

• in-degree (v6) - 2
• out-degree (v1) = 2
• Sum of in-degrees = |E|
• Sum of out-degrees = |E|
• Max no of edges = |V| * (|V| - 1)