Given a graph G, $T={v|d_G(v)\equiv1\ mod\ 2}$, a subgraph P is called a parity subgraph if
$G-E(P)$ is an even subgraph ( i.e. every vertex of G-E(P) has even degree)
Problem: To find a parity subgraph with the minimum number of edges.
More general, let $T\subset V(G)$, a set of edges $J$ is called a $T$-join if all the edges of $J$ induce a subgraph, s.t. $d_J(v)\equiv1\ mod\ 2\Leftrightarrow v\in T$, A parity subgraph of G is a $T$-join of G where $T={v|d_G(v)\equiv1\ mod\ 2}$
Problem: To find a $T$-join with the minimum number of edges.
Bipartite Graph
A graph is bipartite if its vertex set can be partitioned into two sets X and Y such that every edge of G joins a vertex of X and a vertex of Y.
For example.
Proposition. A graph is bipartite $\Leftrightarrow$ it has no odd cycles
Proof
$\Rightarrow$ Let $G$ be a bipartite graph and let $(X,Y)$ be a bipartition of $G$. Color vertices in X by red and vertices in Y by blue. Let $C$ be a cycle. Then the red vertices and blue vertices appear alternatively on $C$. So $C$ has an even number of vertices. Therefore, $G$ has no odd cycles.
$\Leftarrow$ Let v be a vertex of $G$. Let $X={x|d_G(x,v)\equiv0(mod\ 2)}$ and $Y={y|d_G(y,v)\equiv 1(mod\ 2)}$
Since $G$ has no odd cycle, there is no edges joining two vertices from the same part. So G is bipartite.
Every part in the bipartition induce the graph without edges.
A vertex subset $I$ of $V(G)$ is independent if $G$ has no edges joining any two vertices of $I$.
The maximum cardinality of independent sets is called the independent number of $G$.
Problem: Determine the independent number of a given graph $G$ (NPC)If G is bipartite, the its independent number $\alpha(G)\geq\frac{n}{2}$.
**(The Four color problem) Every graph drawn on the plane without crossing edges has a vertex partition into four independent sets.According to the above, if G is a plane graph, $\alpha(G)\geq\frac{\lvert V(G)\rvert}{4}$**
Second Proof of the Mantel’s Theorem
Recall: Let G be an n-vertex graph without triangle, then $\lvert E(G)\rvert\leq\frac{n^2}{4}$Let x be a vertex of G such that $d_G(x)=\Delta(G)$. So $N_G(x)$ is an independent set of G.
and equality holds $\Leftrightarrow n-d_G(x)=d_G(x),\ i.e.\ d_G(x)=\frac{n}{2}$
Degenerated Graph
A graph G is k-degenerate if every subgraph of G has a vertex of degree at most k. A tree is 1-degenerate
A graph G is k-colorable if the vertex of G can be colored by k different colors such that any vertex subset with same color is an independent set. i.e. the vertex set of G can be partitioned into k independent subsets.
Proposition: A k-degenerated graph is (k+1)-colorable
Proof. Let G be k-degenerate graph. Then G has a vertex v of degree at most k.
Use induction on the number of vertex.
The inductive hypothesis implies that $G-v$ is (k+1)-colorable. All vertices in $N_G(x)$ have been colored by at most k different colors in any (k+1)-coloring of G-v. Then color v by the (k+1)th color. So G is (k+1)-colorable.
1-factor is a spanning subgraph in which every vertex has degree one. 1-degenerate graph is a tree(or a forest)
Corollary. Every graph G is $(\Delta(G)+1)$-degenerate
Def. A Planar graph is a graph with a drawing on the plane $\mathbb{R}^2$ . A connected region of $\mathbb{R}^2-G$ is a face of G.
Thm(Euler Formula) Let G be a planar graph, and let n,m and f be the numbers of vertex,edges and faces of G, Then
Proposition. Every planar graph is 5-degenerate
Proof. Let G be a planar graph. It suffices to show that G has a vertex of degree at most five. Without loss of generality, assume that G is a maximal planar graph (i.e. every face is bounded by a triangle). Otherwise, we can add edges to G to keep it to be a planar graph.
Since every edge appears on the boundaries of two faces and every face contains exactly three edges, it follows that
Let $\delta=\delta(G)$, the minimum degree of G, then
By Euler’s Formula: $n-m+f=2$
Therefore, $\frac{2}{\delta}-\frac{1}{3}>0\Rightarrow \delta<6\Leftrightarrow \delta\leq5$
Every planar graph has a vertex of degree at most 5, which implies a planar graph is 5-degenerate.
Corollary. Every planar graph is 6-colorable.
Actually we can use Kempe chain to prove the proposition that every planar graph is 5-colorable.Problem:What kind of Eulerian graphs having an even-cycle decomposition?
Conjecture(Akiyama,1980s) Every planar graph with n vertices has an induced 2-degenerate graph with at least n/2 vertices.
Conjecture(Albertson&Berman,1970s) Every planar graph with n vertices has an induced 1-degenerate graph with at least n/2 vertices.
Matrices and Graphs
A square matrix A is symmetric if $A^T=A$
A scalar $\lambda$ is eigenvalue of A if there exists a non-zero vector $\vec{X}$, s.t. $A\vec{X}=\lambda\vec{X}$ and $\vec{X}$ is called an eigenvector of A with respect to $\lambda$.
A basis $B$ of a vector space is orthonormal if $||\vec{X}||=1$ for any $\vec{X}\in B$, and $<\vec{X_1},\vec{X_2}>=0$ for any $\vec{X_1},\vec{X_2}\in B$
Thm. Let A be a real symmetric $(n\times n)$-matrix. Then A is a diagonizable and $\mathbb{R}^n$ has orthonormal basis of eigenvectos of A
Proposition. All eigenvalues of a real symmetric $(n\times n)$-matrix is real
Proof We assume that A is a $n\times n$ matrix, $\lambda$ is an eignevalue of A.
Assume that $\vec{X}$ is an eigenvector of $\lambda$, Then
So $\lambda=\bar{\lambda}\Rightarrow\lambda$ is real.
A real symmetric matrix A is positive semi-definite if ,for all $\vec{X}\in\mathbb{R}^n$, $\vec{X}^TA\vec{X}\geq0$ and A is positive definite if $\vec{X}^TA\vec{X}>0$
Proposition. All eigenvalues of a positive semi-definite $\Leftrightarrow\ \exists$ a matrix B, s.t. $A=B^TB$
Proof.$\Rightarrow$ We assume that A is a positive semi-definite matrix.
Then A is diagonaizable and assume that $A=Q^TDQ$ where D is a diagonable matrix with eigenalues on its diagonal. Note that all egienvalues of A are non-negative.
$\Leftarrow$ Let $A=B^TB$.
Then for any $\vec{X}\in\mathbb{R}^n$, $\vec{X}^TA\vec{X}=\vec{X}^TB^TB\vec{X}=(B\vec{X})^TB\vec{X}=||B\vec{X}||\geq0$
So A is positive semi-definite.