Def. A graph is a discrete structure/combinational structure consisting of vertices and edges which connect to a pair of vertices.
Usually, a vertex is represented by a dot and an edge is represented by a line (straight or curved) joining two vertices.
A vertex is incident with an edge if the edge join the vertex to another vertex, which is also called the end of the edge.
Two vertices are adjacent to each other if there is an edge joinging them.
The vertex u is adjacent to the vertex v because uv is an edge of G
A graph is simple if there is at most one edge between any two vertices and there is no edge joining a vertex itself.
In short, a graph is simple if and only if it has no multi-edges and no loops.Next, unless otherwise specified, we will discuss simple graphs by default.
For any given simple graph $G(V,E)$，V is the vertex set and E is the edge set.
A graph is complete if the graph has an edge between every pair of vertices.A complete graph of n vertices is usually denoted by $K_n$
The degree of a vertex v of G, denoted by $d_G(v)$, is the number of edges incident with it.
The maximum degree of G is defined as $\Delta(G):=\max{d_G(x)|v\in V(G)}$
The minimum degree of G is defined as $\delta G:=\min{d_G(v)|v\in V(G)}$
The average degree of G is defined as $d(G):=\frac{\lvert E(G)\rvert}{\lvert V(G)\rvert}$, this index is used to measure the density of the graph.According to this index, graph can be divided into dense graph and sparse graph
A neighbor of v in G is a vertex joined to v by an edge of G.The neighborhood of a vertex v in G is the set of all neighbors of v in G, denoted by $N_G(v)={u|u\in V(G),uv\in E(G)}$.We have $d_G(v)=\lvert N_G(v)\rvert$ easily.
Here we give the set representation of neighbors:
$N_1(v)=N_G(v),N_2(v)=N_G(N_1(v))-N_1(v)\cup\{v\},\ N_3(v)=N_G(N_2(v))-N_1(v)$
and if $w\in N_3(v),\ distance(w,v)=3$
A graph is even if every vertex of G has an even degree.
Proposition(Handshaking Lemma)
Every graph has an even number of vertices with odd degree.
Proof.
Let
Then,$\sum{x\in X}d_G(x)+\sum{y\in Y}d_G(y)=2\lvert E(G)\rvert$
So, $\sum_{y\in Y}d_G(y)\equiv0(mod\ 2)$.It follows immediately that $\lvert Y\rvert\equiv0(mod\ 2)$
So the proposition holds.
Question:Let G be an n-vertex graph.How many edges will force G to have a triangle?(Mantel’s Theorem)
Def A walk of G is a sequence of vertices and edges of Gsuch that (i)both the first element and the last element of the sequence are vertices and (ii) any two consecutive elements in the sequence contains one vertex and one edge which are incident with each other.
For walk,vertex can be repeated, edge can be repeated.
A walk is open if the first vertex is not equal to the last vertex. $w_0=v_2e_2v_3e_3v_4e_4v_2e_1v_1$
A walk is a trail if it does not have repeated edges. $w_0$ is a trail
A trail is a path if it does not have repeated vertices.
$w_3=v_1e_1v_2e_2v_3e_3v_4=v_1v_2v_3v_4$ is a pathA cycle is a closed trail( or path) without repeated vertices (vertices and edges) except the first vertex and the last vertex. $w_4=v_2e_2v_3e_3v_4e_4v_2$
A graph is connected if for any two vertices x and y, there is a path joining x and y.
A subgraph H of G is a graph with $V(H)\subset V(G),E(H)\subset E(G)$
A maximal connected subgraph of G is called a connected component. Maximal means anything bigger than it is not connected
An edge e of G is bridge or cut-edge if #connected components of G-e>#connected components of G
Both $e_1$ and$e_2$ are bridges/cut-edges
Thm(BJJ,Fan)
Every graph without bridges has a family of cycles which covers every edge exactly 2k times for any integer $k\ge2$
A subgraph H is spanning if $V(H)=V(G)$
A subgraph H is induced by $S\subset V(G)$, if $V(H)=S$ and for any two vertices $x,y\in S$, $xy\in E(H)\Leftrightarrow xy\in E(G)$
A subgraph H is induced by $S\subset E(G)$, if $E(H)=S$ and $v\in V(H)$a if and only if v is incident with an edge in S.
Let $x,y\in V(G)$, the distance between x and y in G is the length of the shortest path joining x and y, denoted by $dist_G(x,y)$. In other words,
