Discrete-math 12

Discrete maths Exercise 12

|ProofDisproofQuestion no. and sectionXWarm-up, question 1XWarm-up, question 2XWarm-up, question 3XWarm-up, question 4XWarm-up, question 5XNot warm-up, question 1aXNot warm-up, question 1bXNot warm-up, question 2XNot warm-up, question 3XNot warm-up, question 6XNot warm-up, question 7aXNot warm-up, question 7bXNot warm-up, question 7cXNot warm-up, question 8aXNot warm-up, question 8bXNot warm-up, question 9aXNot warm-up, question 9bXNot warm-up, question 10aXNot warm-up, question 10bXNot warm-up, question 10cXNot warm-up, question 10d|

Warm-up

Let G=(V,E)Prove or disprove that exists a simple graph such that the degrees of it’s vertices are:

1

5,5,5,5,5,5,5,5Proof:V={v1,v2,…,v8}By the Hand-Shaking lemma: ∑v∈Vdeg(v)=2⋅|E|∑v∈Vdeg(v)=5⋅|V|=5⋅8=40⟹2⋅|E|=40⟹|E|=20G has 8 vertices⟹maximum number of edges in G is 8⋅72=562=28And there are at least two vertices with the same degree⟹G might exist
graph LR;

1
1---2
1---3
1---4
1---5
1---7

2
2---5
2---7
2---8
2---4

3
3---7
3---6
3---5
3---8

4
4---5
4---6
4---8

5
5---6

6
6---8
6---7

7
7---8

8

%% linkStyle 0,1,2,3,4 stroke:purple;
%% linkStyle 5,6,7,8 stroke:red;
%% linkStyle 9,10,11,12 stroke:green;
%% linkStyle 13,14,15 stroke:blue;
%% linkStyle 16 stroke:orange;
%% linkStyle 17,18 stroke:cyan;

2

1,2,2,3,4,5Disproof:V={v1,v2,…,v6}∑v∈Vdeg(v)=1+2+2+3+4+5=17⟹2⋅|E|=17⟹G doesn’t exist

3

1,1,2,3,4,5Disproof:Let such a graph existV={v1,v2,…,v6}∑v∈Vdeg(v)=1+1+2+3+4+5=17⟹2⋅|E|=16⟹|E|=8Let us try to build this graph:Let deg(v1)=5WLOG⟹{v2,v1},{v3,v1}∈ELet deg(v2)=deg(v3)=1WLOGThis means, that there can be no more edgesgoing to v1,v2 or v3⟹In a subgraph G′=({v4,v5,v6},E′) there is a vertex with degree 4We can subtract one for the edge that is already there⟹In a simple graph with 3 vertices there is a vertex with degree 3Contradiction!⟹G doesn’t exist

4

2,2,2,2,3,3Proof:V={v1,v2,…,v6}∑v∈Vdeg(v)=2+2+2+2+3+3=14⟹2⋅|E|=14⟹|E|=7And there are at least two vertices with the same degree⟹G might exist
graph LR;

1---2
1---3
2---4
2---5
3---5
5---6
4---6

5

Simple graph with 100 vertices such that for every 1≤k≤5there are 20 vertices of degree kProof:G is a graph containing 10 of the following connected components:
graph LR;

5---6
4---5
3---4

1---2
1---3
1---4
1---5
1---6

6---7
7---8

5---10
6---10
7---10
8---10
9---10

Not warm-up

1a

Let G=(V,E)Prove or disprove:if ∀u,v∈V:(u,v)∉E∧deg(v)+deg(u)≥|V|−1⟹G is connectedProof:Let |V|=nLet ∀u,v∈V:(u,v)∉E∧deg(v)+deg(u)≥|V|−1Let δG=0⟹Maximum degree is n−2∃u,v∈V:deg(v)=δG⟹δG+deg(u)≥n−1⟹deg(u)≤n−2 and deg(u)≥n−1− Contradiction!⟹δG≥1Let {u,v}∉EThere are n−2 vertices besides u,vdeg(v)+deg(u)≥n−1⟹There are n−1 edges and n−2 possible "destinations"⟹By the pigeonhole principle, there are at least 2 edges going to the same vertexThere can be no more than one edge from one vertex to another⟹These 2 edges are {v,w},{w,u}⟹w∈Γ(v)∩Γ(u)⟹u,v are in the same connected component⟹G is connected

1b

Let G=(V,E)Prove or disprove: G is connected⟺∃u,v∈V:deg(v)deg(u)≥|V|2−|V|Disproof:Let |V|=nLet u,v∈Vdeg(u)≤n−1deg(v)≤n−1⟹deg(u)deg(v)≤(n−1)(n−1)<n(n−1)=n2−n=|V|2−|V|⟹∃u,v∈V:deg(v)deg(u)≥|V|2−|V| is always False (a contradiction)But "G is connected" is not a contradiction

2

Prove by induction there for any tree with n≥2 vertices has at least 2 leaves.Proof:Base case. Let n=2The only tree with 2 vertices is the one with an edge between them:G=({v1,v2},{{v1,v2}})deg(v1)=deg(v2)=1⟹There are 2 leavesInduction step. Let the stated hold for any tree with n verticesLet G=(V,E) be a tree with n+1 verticesLet v∈V,deg(v)=δGG is a tree⟹G is connected⟹δG≥1⟹deg(v)>0Every tree has at least 1 leaf⟹δG=1⟹deg(v)=1Let u∈Γ(v)G′=G∖{v} is a tree with n vertices⟹G′ has at least 2 leavesIf u is not a leaf of G′, then G has at least 2 leaves from G′ and leaf vIf u is a leaf of G′, then G has at least 1 leaf from G′ and leaf v⟹G has at least 2 leavesBase case + Induction step⟹Proved by Induction

3

Prove: undirected graph G = (V, E) is a tree iffthere exists a single simple path between any of it’s verticesProof:Let G=(V,E) is a treeLet u,v∈VG is connected⟹exists a simple path from u to vLet there exist 2 different paths from u to v⟹exists a simple path (u,…,v,…,u) which is a cycleG is acyclic−Contradition!⟹Simple path from u to v is uniqueLet there exist a single simple path between any vertices of G=(V,E)⟹G is connected by definitionLet u,v∈VLet there exist a cycle from u to u(u,…,v,…,u)Then there exist two different paths from u to v−Contradiction!⟹G is acyclic⟹G is a tree

4

An undirected, acyclic graph is called a forest.Let G=(V,E) be a forest with c connected components.Find a closed formula for |E|Solution:Forest is a graph where each connected component is a treeLet G1=(V1,E1),…,Gc=(Vc,Ec) be connected components of G⋃i=1cVi=V∀i,j∈[1,c]:i≠j⟹Vi∩Vj=∅⟹|V|=|⋃i=1cVi|=∑i=1c|Vi|⋃i=1cEi=E∀i,j∈[1,c]:i≠j⟹Ei∩Ej=∅Any tree has exactly n−1 edges, where n is the number of vertices in this tree⟹|E|=|⋃i=1cEi|=∑i=1c|Ei|=∑i=1c(|Vi|−1)=∑i=1c|Vi|−c⟹|E|=|V|−c

5a

How many connected components does an undirected acyclic graph G=(V,E) with|E|=10,|V|=17 have?Solution:G is a forest⟹|E|=|V|−c, where c is a number of connected components⟹10=17−c⟹c=7⟹G has 7 connected components

5b

What is the minimal number of edges in an undireced graph G=(V,E)with |V|=n and diam(G)=2Solution:diam(G)=2⟹G is connected⟹|E|≥n−1Is there such a graph with exactly n−1 edges?Yes, the star graph, where one vertex is connected to all othersand no other edges are present⟹The minimal number of edges is n−1

6

Let G=(V,E) be a finite simple undirected connected graphwith a single cycle with |V|≥3Prove: |V|=|E|Proof:Let {u,v} be an edge in the cycle of GIf we remove this edge, we get an acyclic connected graph⟹G′=(V,E∖{{u,v}}) is a tree⟹|E∖{{u,v}}|=|V|−1=|E|−1⟹|V|=|E|

7a

Prove or disprove: there exists a tree graph with degrees of vertices as following:1,1,4,3,3,1,1Disproof:Let G=(V,E)∑v∈Vdeg(v)=1+1+4+3+3+1+1=14⟹2⋅|E|=14⟹|E|=7=|V|⟹G has a cycle⟹G is not a tree

7b

Prove or disprove: there exists a tree graph with degrees of vertices as following:1,1,3,1,3,1,2Proof:
graph LR;
1(1)
2(2)
3(3)
4(4)
5(5)
6(6)
7(7)

1---3
2---3
3---5
5---6
5---7
7---4

7c

Let V={1,2,…,n}Let {d1,d2,…,dn}⊆N∑i=1ndi=2n−2Prove: there exists a tree graph with vertices V such that their degrees are d1,d2,…,dnProof:Let G=(V,E)|V|=n∑v∈Vdeg(v)=∑i=1ndi=2n−2=2(n−1)=2⋅|E|⟹|E|=n−1Base case. Let n=1One vertex with degree 0 is a tree ∑v∈Vdeg(v)=0=2n−2Induction step. Let the statement hold for nLet G=(V,E) be a tree graph satisfying the conditions with n verticesG is a tree⟹∃v∈V:deg(v)=1Let u∉VLet G′=(V∪{u},E∪{v,u})G′ is also a tree∑w∈V∪{u}deg(w)⏟degrees in graph G′=∑w∈Vdeg(w)⏟degrees in graph G+deg(u)⏟just 1+1⏟1 new edge from v=2n−2+2=2n==2(n+1)−2⟹There exists a tree graph such that the condition holds for n+1 vertices⟹Proved by Induction

8a

Let G=(V,E) be a connected graphProve: |V|=n+1,|E|=n⟹∃v∈V:deg(v)=1Proof:Let |V|=m|E|=m−1⟹Removing any edge will make G disconnected⟹G is a minimal connected graphSuppose G has a cycleRemoving any edge from this cycle would still leave G connected−Contradiction!⟹G has no cycles⟹G is a tree⟹G has at least two leaves⟹∃v∈V:deg(v)=1

8b

Let G=(V,E) be a connected graphProve: |V|=n,|E|=n−1⟹G is acyclicProof:Same proof as in 8aLet |V|=n|E|=n−1⟹Removing any edge will make G disconnected⟹G is a minimal connected graphSuppose G has a cycleRemoving any edge from this cycle would still leave G connected−Contradiction!⟹G has no cycles

9a

Let G=(V,E) be a finite simple graphLet U={v∈V|deg(v) is odd}Prove: |U| is evenProof:2⋅|E|=∑v∈Vdeg(v)=∑v∈Udeg(v)+∑v∈V∖Udeg(v)⏟even⏟even⟹∑v∈Udeg(v) must also be evenSum of odd integers is only even when the number of such integers is even⟹|U| is even

9b

Prove:If G is connected and there exists an edge e such that G′=(V,E∖{e}) is not connectedThen ∃v∈V:deg(v) is oddProof:Let G=(V,E) be a connected graphLet e={u,v}∈ELet G′=(V,E∖{e}) be a not connected graphLet ∀v∈V:deg(v) is even in GWe can state the following to be true:1.Degrees of u and v are odd in G′2.Degrees of all other vertices are even3.u and v are now in two different connected componentsLet Gv′=([v]∼,Ev) be a subgraph over the connected component of vWhere Ev={{x,y}|x,y∈[v]∼}By the hand shaking lemma:2⋅|Ev|=∑x∈[v]∼deg(x)=∑x∈[v]∼∖{v}deg(x)⏟even+deg(v)⏟odd, which is odd−Contradiction!⟹∃v∈V:deg(v) is odd

10a

Prove or disprove: if G is connected, then G― is not connectedDisproof:
graph LR;
	subgraph G
		1(1)
		2(2)
		3(3)
		4(4)
		
		1---2
		1---3
		3---4
		linkStyle 0,1,2 stroke:red;
	end
	subgraph G-complement
		1'(1)
		2'(2)
		3'(3)
		4'(4)
		
		1'---4'
		2'---3'
		2'---4'
		%% 1'-.-2'
		%% 1'-.-3'
		%% 3'-.-4'
		linkStyle 3,4,5 stroke:blue;
		%% linkStyle 6,7,8 stroke:red,stroke-width:0.8px;
	end
	G---->G-complement

10b

Prove or disprove: if G is not connected then G― is connectedProof:Let G be disconnected⟹G has at least two connected components⟹There exists a way to divide G into two disjoint graphsLet G1=(V1,E1),G2=(V2,E2) be graphs such that:V1∪V2=VV1∩V2=∅∀v∈V1:∀u∈V2:{u,v}∉E or in other words d(u,v)=∞Let G―=(V,E―) where E―={{u,v}|u,v∈V,{u,v}∉E}⟹∀v∈V1:∀u∈V2:{u,v}∈E― or in other words d(u,v)=1Let v1,v2∈V1 (or V2 which is a symmetrical case)WLOGLet u∈V2u∈Γ(v1),u∈Γ(v2)⟹Exists a simple path (v1,u,v2)⟹d(v1,v2)≤2⟹∀u,v∈V:d(u,v)<∞ in G―⟹G― is connected

10c

Prove or disprove: if G is regular, then G― is also regularProof:Let G=(V,E)Let |V|=nLet ∀u,v∈V:deg(u)=deg(v)=kLet G―=(V,E―)Let v∈VΓ(v) in G― is equal to V∖(Γ(v)∪{v}) in Gv∉Γ(v),Γ(v)⊆V⟹|V∖(Γ(v)∪{v})|=|V|−(|Γ(v)|+1)=|V|−deg(v)−1==n−k−1⟹∀v∈V:deg(v)=n−k−1 in G―⟹G― is regular

10d

Let G=(V,E)Let |V|=6Prove or disprove: either G or G― has a triangle (a cycle of length 3)Proof:Let v∈VThere are 5 other vertices in VAny vertex can either be a neighbor of v in G or be a neighbor of v in G―⟹By the pigeonhole principle v has at least 3 neighbors in either G or G―Let deg(v)≥3 in G(WLOG)Let x,y,z∈V be the three neighbors of vIf any of edges {x,y},{x,z},{y,z} are in EThen G has a triangle (v,x,y),(v,x,z) or (v,y,z)If none of these edges are in EThen all of them are in E― and G― has a triangle (x,y,z)
graph LR;

subgraph G
	1(v)
	2(x)
	3(y)
	4(z)
	5(u)
	6(w)
	
	1---2
	1---3
	1---4
	1---5
	1---6
	linkStyle 0,1,2 stroke:red;
	linkStyle 3,4 stroke:blue;
end

subgraph G1
	2'(x)
	3'(y)
	4'(z)
	
	2'---3'
	3'---4'
	4'---2'
	linkStyle 5 stroke:red;
	linkStyle 6,7 stroke:blue;
end

subgraph G2
	2''(x)
	3''(y)
	4''(z)
	
	2''---3''
	3''---4''
	4''---2''
	linkStyle 8,9,10 stroke:blue;
end

G-->G1
G-->G2