Simple Graph

A graph is called a simple graph if it ⇒ does not contain multiple edges between the same pair of vertices ⇒ does not contain loops

Properties

• Vertexes → $n$
• Edges
  • min→ $0$
  • max → $n-1$
• Degree ranges → Degrees of $\forall v\in V(G)$ can range over $\{0, ...,n-2\}$ OR $\{1, ...,n-1\}$

Cycle graph

A graph that consists of a single cycle with $n$ vertexes denoted by $C_n$

Properties

• Vertexes → $n$
• Edges → $n$
• Chromatic number , Chromatic Index

$$ \chi ( C_{n})=\chi' ( C_{n}) =\begin{cases} 3 & \text{if} \ n\ \text{is odd}\\ 2 & \text{otherwise} \end{cases} $$

$k$-connected graph

Conventional definition A graph where $\kappa(G)\geq k$ (for graph to be disconnected we must remove at least $k$ vertexes)

Mengers theorem definition Graph with at least two vertices is $k$-connected if, for every pair of its vertices, it is possible to find $k$ vertex-independent paths connecting these vertices.

Complete Graph