Discrete-math 21

Discrete-math 21

Graph #definition

Graph is a set of points and linesGraph is an ordered pair of set of vertices and set of edgesG=(V,E)E⊆{{v,u}|v,u∈V,v≠u}E is a set of unordered pairs of distinct verticesIn this case, G is a simple undirected graph

Adjacency #definition

Vertices u,v∈V are called adjacent if they have a common edge(if they are connected by some edge e∈E)e is then called incident on u,v
What is the max number of edges in a simple graph with n vertices(n2)=n!(n−2)!2!=n(n−1)2What is the number of simple graphs with n vectices?2(n2)=2n(n−1)/2
Let G=(V,E),v∈V

Neighborhood of a vertex and of a set of vertices #definition

Neighborhood of vertice v is a set of vertices which are adjacent to vΓ(v)={u∈V|{u,v}∈E}Let S⊆VNeighborhood of set of vertices S is a set of verticeswhich are adjacent to at least one of vertices in SΓ(S)={u∈V|∃v∈S:{u,v}∈E}

Degree of vertex #definition

Degree of vertice v is a size of neighborhood of vdeg(v)=|Γ(v)|

Hand-shaking lemma for graphs #lemma

Let G=(V,E) be a simple graphThen ∑v∈Vdeg(v)=2⋅|E|Proof:Each edge is counted twice in ∑v∈Vdeg(v)Each edge is counted twice in 2⋅|E|⟹∑v∈Vdeg(v)=2⋅|E|

Corollary of this lemma

In any simple graph, number of vertices with odd degree is evenProof:Let ODD={v∈V|deg(v) is odd}Let EVEN={v∈V|deg(v) is even}ODD∪EVEN=V,ODD∩EVEN=∅Let |ODD| be oddThen 2⋅|E|=∑v∈Vdeg(v)=∑v∈ODDdeg(v)+∑v∈EVENdeg(v)Sum of odd number of odd numbers is oddSum of even numbers is even⟹∑v∈ODDdeg(v) is odd∑v∈EVENdeg(v) is even⟹∑v∈ODDdeg(v)+∑v∈EVENdeg(v)=∑v∈Vdeg(v)| is odd⟹2⋅|E| is odd−Contradiction!⟹|ODD| is even

Equal degree vertices #lemma

In each simple graph G=(V,E)with at least 2 vertices there are two vertices u≠v∈V:deg(u)=deg(v)Proof:Case 1. There is a vertex v:deg(v)=n−1Then there is no vertex u:deg(u)=0⟹Possible degrees are from 1 to n−1The number of vertices is n, the number of different degrees is n−1⟹By the pigeonhole principle there is at least two vertices with the same degreeCase 2. There is no vertex v:deg(v)=n−1⟹Possible degrees are from 0 to n−2The number of vertices is n, the number of different degrees is n−1⟹By the pigeonhole principle there is at least two vertices with the same degree

Paths #definition

Let G=(V,E)Path is a sequence of vertices (v1,v2,…,vk+1) such that ∀i∈[1,k]:{vi,vi+1}∈EPath is called simple if no vertices appear in the path more than onceLength of the path (v1,v2,…,vk+1) is the number of edges in this path, which is k

Cycle #definition

Path (v1,v2,…,vk+1) is called a cycle if v1=vk+1Cycle is called simple if no vertices except v1,vk+1 appear in the cycle more than once

Distance #definition

Let v,u∈VDistance from v to u is the length of the shortest path from v to ud(v,u)If there is no path between vertices v,u∈V then d(v,u)=∞

Diameter of graph #definition

Diameter of graph G=(V,E)is a minimal distance between two distinct vertices of the graphdiam(G)=maxu,v∈V(d(v,u))

Diameter of "tight" graph #lemma

Let G=(V,E) be a simple graph such that,∀v∈V:deg(v)≥n−12Then diam(G)≤2Proof:Let v,u∈VCase 1. v=u⟹d(v,u)=0⟹d(v,u)≤2Case 2. {v,u}∈E⟹d(v,u)=1⟹d(v,u)≤2Case 3. Γ(v)∩Γ(u)≠∅∃w∈V:w∈Γ(v)∩Γ(u)⟹∃{w,v},{w,u}∈E⟹(v,w,u) is a path⟹d(v,u)≤2Case 4. Γ(v)∩Γ(u)=∅u∉Γ(v),u∉Γ(u)v∉Γ(u),v∉Γ(v)n=|V|≥|Γ(v)|⏟≥n−12+|{v}|+|Γ(u)|⏟≥n−12+|{u}|≥(n−1)+2=n+1n≥n+1−Contradiction!⟹∀v,u∈V:d(v,u)≤2⟹diam(G)≤2