Lecture series on graph theory 2

First, we try to prove the Mantel’s Theorem, which was presented as a question in the last blog post.

Thm(Mantel’s Theorem)
Let G be a graph with n vertices. If G does not contain a triangle, then

$\lvert E(G)\rvert\leq\frac{n^2}{4}$

Before the proof begin, we introduce what triangle means.

$C=v_1v_2v_3v_4v_5v_1$ is a 5-cycle.Generally, k-cylce has k vertices.Specially, we call a 3-cycle as a triangle

Now, let’s take a few examples to find potential patterns which may help to prove this theorem.

In general, we can divide n vertices into two groups, then we add all edges between two groups.Because there is no edge joining the vertices from the same side, if there is a cycle in graph, it must be an even cycle, such as alternating left-hand and right-hand sides.
If n is even, #edges=$\frac{n}{2}\cdot\frac{n}{2}=\frac{n^2}{4}$, if n is odd, #edges=$\frac{n+1}{2}\cdot\frac{n-1}{2}=\frac{n^2-1}{4}\leq\frac{n^2}{4}$

Proof of the Mantel’s Theorem

Let G be an n-vertex graph without a triangle.

$\forall x,y\in V(G)$, if $xy\in E(G)$, $N_G(x)\cap N_G(y)=\emptyset$ because G has no triangle.

Because $N_G(x)\cup N_G(y)\subset V(G)$, $d_G(x)+d_G(y)\leq n$

From the above formula, we have

$\sum_{xy\in E(G)}(d_G(x)+d_G(y))\leq\sum_{xy\in E(G)}n=n\cdot\lvert E(G)\rvert \tag{1}$

We find that $dG(x)$ appears in $d_G(x)+d_G(y_1),d_G(x)+d_G(y_2),\dots,d_G(x)+d_G(y{d_G(x)})$

$So\ \sum_{xy\in E(G)}(d_G(x)+d_G(y))=\sum_{x\in V(G)}d_G(x)\cdot d_G(x)=\sum_{x\in V(G)}d_G(x)^2\tag{2}$

From (1) & (2), we have

$\sum_{x\in V(G)}d_G(x)^2\leq n\cdot\lvert E(G)\rvert\tag{3}$

According to the relationship between degree and edge: $\sum{x\in V(G)}d_G(x)=2\lvert E(G)\rvert$ and the Cauchy-Schwarz inequality:$(\sum{k=1}^n ak^2)(\sum{k=1}^n bk^2)\geq(\sum{k=1}^na_kb_k)^2$, we have

$\sum_{x\in V(G)}d_G(x)^2\geq \frac{(\sum_{x\in V(G)}d_G(x))^2}{n}=\frac{4\lvert E(G)\rvert^2}{n}\tag{4}$

From (3) & (4), $\frac{4\lvert E(G)\rvert^2}{n}\leq \sum_{x\in V(G)}d_G(x)^2\leq n\cdot \lvert E(G)\rvert$ which implies $\lvert E(G)\rvert \leq\frac{n^2}{4}$

If a graph G has more than $\frac{n^2}{4}$ edges, then G has a triangle.

Furthermore, we can extend the triangle to k-cycle and obtain the Erdős-Gallai's Theorem
We can also extend the triangle to a complete graph with k vetices, which are called k-clique and obtain the Turán's Theorem

Tree: A tree is a connected graph without cycles.

Proposition: Every tree with at least two vetices has at least two vertices of degree one

Proof

Let P be the longest path of G. Then both end vertices of P have degree one in G.If not, we suppose that $u,v\in V(P),\ uv\in E(P)$ and u is the end vertex of P, but $d_G(u)>1$.

Case 1:

$w\not\in V(P)$ and $wu\in E(G)$,then $\tilde{P}=P+wu$ is longer than P. This contradicts the fact that P is the longest path.

Case 2:

$w\in V(P),w\not=v$ and $wu\in E(G)$, then we can find that there is a cycle. This contradicts the fact that G is a tree.

A vertex of a tree is a leaf if it has degree one.

Proposition: A connected graph with n vertices is a tree if and only if it has n-1 edges.

Proof

$\Rightarrow$ n=1, G has no edges.

Now, we assume that it is correct for a tree with n-1 vertices to have n-2 edges.From this assumption, we want to deduce that a tree with n vertices has n-1 edges.

Since $n\ge2$, G has a vertex v of degree one. Let u be the only neighbor of v in G. Because G is a tree with n vertices, G-v is a tree with n-1 vertices. According to the asssumption,$\lvert E(G-v)\rvert=(n-1)-1$.

$\lvert E(G)\rvert=\lvert E(G-v)\rvert+1=(n-1)-1+1=n-1$

$\Leftarrow$ Let G be a connected graph with n vertices and n-1 edges. We claim that G has a vertex of degree one.

We prove this claim first.If not, $\forall x\in V(G)$, assume $d_G(x)\ge2$

Then we have $\lvert E(G)\rvert=\frac{1}{2}\sum_{x\in V(G)}d_G(x)\ge\frac{1}{2}\cdot2\lvert V(G)\rvert=n>n-1$ which contradicts that $\lvert E(G)\rvert=n-1$. The contradiction implies the claim holds.

From this claim, G has a vertex of degree one. Use the induction on G-v. Since G-v has n-1 vertices and $(n-1)-1$ edges. By inductive hypothsis, G-v is a tree and has no cycles.Since v is a degree one vertex, G has no cycles. Therefore, G is a tree.

Corollary: Every graph with minimum degree at least two contains a cycle.

A spanning tree of G is a connected spanning subgraph of G without cycles.

Problem: counting the number of edge-disjoint spanning trees in a graph.
If the number of edge-disjoint spanning trees is large, the graph is well-connected. (Related to edge-connectivity of the graph)

Now we introduce two classic search algorithms in graph theory.

A breadth-first-search tree of a graph (BFS-tree)

(i) Start at $x=x_0$ and join x to all neighbors of x, Let $N_1=N_G(x)$

(ii) For each $y\in Ni$, join y to all neighbors of y without creating cycles and let $N{i+1}=\cup_{y\in N_i}N_G(y)$

The algorithm will take $O (\lvert V\rvert+\lvert E\rvert)$ steps to find a BFS-tree rooted at $x_0$.

A deepth-first-search tree of a graph (DFS-tree)

(i) Start at $x=x_0$ and $T_0={x_0}$

(ii) Join x to one of its neighbor $x_1\in N_G(x_0)$ and$T_1={x_0,x_1}$

(iii) If $Ni=N_G(x_i)\backslash T_i\not=\emptyset$, then join $x_i$ to a vertex $x{i+1}\in Ni$ and let $T{i+1}=Ti\cup{x{i+1}}$ and $x_{i+1}\to x_i$

If $Ni=N_G(x_i)\backslash T_i=\emptyset$, then set $x{i-1}\to x{i}$ and $N{i-1}=NG(x{i-1})\backslash T_i\to N_i$ and continue.

Eulerian graph:

Problem: Let G be a graph.When does G have a closed trail which contains all edges of G?

A closed trail is Eulerian if the trail go through all edges of G. A graph is called Eulerian if it has an Eulerian trail.

Proposition: Every Eulerian graph is a connected graph which has only even-degree vertices

Proof Let G be an Eulerian graph. Then G has an Eulerian trail, denoted by $T=v_1e_1v_2e_2\cdots v_me_mv_1$. So G is connected.

Now, orient the edges of G along the trail T such that, for an edge $ei$ in T, orient $e_i$ from $v_i$ to $v{i+1}$. Since T has no repeated edges, every edge receives exactly one orientation. For each vertex $v_i$, T visits $v_i$ and then leaves $v_i$, which implies

$\# edges\ oriented\ towards\ v_i=\#edges\ oriented\ away\ from\ v_i$

But the degree of $v_i$ satisfies

$\begin{aligned} d_G(v_i)&=\# edges\ oriented\ towards\ v_i+\#edges\ oriented\ away\ from\ v_i\\ &\equiv0(mod\ 2) \end{aligned}$

So every vertex of G has an even degree.

A cycle decomposition D of a graph G is a set of egde-disjoint cycles $D={C_1,C_2,\dots,C_k}$ such that

$\cup_{C_i\in D}E(C_i)=E(G)$

Proposition: Every even graph has a cycle decomposition.

Proof Let G be an even graph. Suppose to the contrary that G does not have a cycle decomposition.

Assume G is a minimal counterexample.If G has a vertex v of degress zero, the G-v is a subgraph of G and hence is not a counterexample. So G-v has a cycle decomposition. So does G, a contradiction to that G is a counterexample.

So assume that$\delta(G)\ge2$. Then by corollary, G has a cycle C. Then, G-E(C) is an even subgraph of G. So G-E(C) has a cycle decomposition D. Then, $D\cup{C}$ is a cycle-decomposition of G, which contradicts that G is a counterexample. So prop. holds.

Corollary: Every Eulerian graph has a cycle decomposition. （conjecture,Hajos,1968）All Eulerian graph with n vertex. How many cycles in a cycle decomposition D?$\lvert D\rvert\le\frac{n-1}{2}$?