---
tags: NTNU,CSIE,必修,Discrete Mathematics
title: Graph
description:
---

{%hackmd @NTNUCSIE112/S1VbPN1HU %}

# Graph
> a set of vertices (or nodes)
a set of edges (or arcs), within which each element specifies whether two vertices are related.

A graph that has neither a loop nor multiple edges in called a **simple** graph.
- loop an edge with identical endpoint.
- multiple edges: edges that connects the same pair of vertices.

A graph is **undirected** if the relation of adjacency is symmetric.
In an undirected graph.
- If two vertices $u$ and $v$ are connected by an edge, we say $u$ and $v$ are adjacent / $u$ is a neighbor of $v$ ($v$ is a neighbor of $u$).
- The number of edges adjcent to vertex $u$ (# neighbor of $u$) is the degree of u, denoted by $deg(u)$(接到幾個邊).
- The set of all neighbors of $u$ is called the neighborhood of $u$, denoted by $N(u)$.

### **Theorem [the handshaking lemma]**.
Let $G = (V, E)$ be an undirected graph.
Then $$\sum_{v \in V} deg(v) = 2|E|.$$
- **Corollary**: An undirected graph has ans even number of vertices of odd degree.
- **Proof** Let G = (V, E) be the undirected graph, and let $V_1$ and $V_2$ be the sets of odd-degree and even-degree vertices, respectively.
- By the handshaking lemma, we have $2|E| = \sum_{v\in V_1}\deg(v) + \sum_{v\in V_2}\deg(v).$
- Since $2|E| - \sum_{v\in V_2}\deg(v)$ is even and $deg(v)$ is odd, for $v \in V_1$, it follows that the number of odd-degree vertices is even.

### **Special types of graphs**
- **Path**: A path on vertices, denoted by $P_n$ si a simple graph consisting of n vertices which can be labeled by $v_1, v_2, \cdots, v_n$ such that $v_i$ is adjacent to $v_{j}$, for $i \in [n-1]$.

- **Cycle**: A cycle on n vertices, denoted by $C_n$, is a simple graph consisting of nn vertices which can be labeled by $v_1, v_2, \cdots, v_n$ such that $v_i$ is adjacent to $v_{j}$, for $i \in [n-1]$, and $v_n$ is adjacent to $v_1$.

- **Complete graph**: A complete graph on n vertices, denoted by $K_n$, is a simple graph in which every pair vertices are adjacent.

- **hypercube**: An n-dimensional hypercube, or n-cube, denoted by $Q_n$, is a graph that has vertices representing the $2^n$ bit string of length n.
- Two vertices are adjacent if the two bit strings differ in exactly one bit position.

- Can you draw $Q_4$ ?
- There are $2^4$ vertices. (16個)
- How many edges are there? (32個)
- What is the degree of a vertex (handshaking lemma).

- **bipartite graph**: A simple graph G is bipartite if its vertex set can be separated into two set $A,B$ and
$$V_1 \in A, V_2 \in B$$
$$\forall \exists V_1 \rightarrow V_2, V_2 \leftarrow V_1
$$

### Question
1. $n \in \mathbb{N}\ P_n$ is a bipartite? 是
2. $n \geq 3 \in \mathbb{N}\ C_n\text{? when } n$ = 偶數 是
3. $Q_n?$ 是
4. $K_n?$ 不是