[PDF] Mathematics 1 Part I: Graph Theory Exercises and problems

View - Download Mathematics 1 Part I: Graph Theory Exercises and problems

Previous PDF

Next PDF

Bachelor Degree in Informatics Engineering

Facultat d'Informatica de Barcelona

Mathematics 1

Part I: Graph Theory

Exercises and problems

February 2023

Departament de Matematiques

Universitat Politecnica de Catalunya

The problems of this collection were initially gathered by Anna de Mier and Montserrat Mau- reso. Many of them were taken from the problem sets of several courses taught over the years by the members of the Departament de Matematica Aplicada 2. Other exercises came from the bibliography of the course or from other texts, and some of them were new. Since Mathematics

1 was rst taught in 2010 several problems have been modied or rewritten by the professors

involved in the teaching of the course. We would like to acknowledge the assistance of the scholar Gabriel Bernardino in the writing of the solutions. Translation by Anna de Mier and the scholar Bernat Coma. This problem list has been revised during the academic years 2018/2019 and 2022/2023.

Contents

1 Graphs: basic concepts 1

1.1 Types of graphs. Subgraphs. Operations with graphs.:: :: :: :: :: :: ::1

1.2 Exercises:: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: :: ::3

2 Walks, connectivity and distance 7

3 Eulerian and Hamiltonian graphs 10

4 Trees12

Review exercises 15

1

Graphs: basic concepts

1.1 Types of graphs. Subgraphs. Operations with graphs.

The following are some important families of graphs that we will use often. Letnbe a positive integer andV=fx1;x2;:::;xng. Thenull graphof ordern, denoted byNn, is the graph of ordernand size 0. The graph N

1is called thetrivial graph.

Thecomplete graphof ordern, denoted byKn, is the graph of ordernthat has all possible edges. We observe thatK1is a trivial graph too. Thepath graphof ordern, denoted byPn= (V;E), is the graph that has as a set of edges

E=fx1x2;x2x3;:::;xn1xng.

Thecycle graphof ordern3, denoted byCn= (V;E), is the graph that has as a set of edgesE=fx1x2;x2x3;:::;xn1xn;xnx1g. Thewheel graphof ordern4, denoted byWn= (V;E), is the graph that has as a set of edgesE=fx1x2;x2x3;:::;xn1x1g [ fxnx1;xnx2;:::;xnxn1g.

Letrandsbe positive integers.

A graph isr-regularif all vertices have degreer.

A graphG= (V;E) isbipartiteif there are two non-empty subsetsV1andV2such that V=V1[V2,V1\V2=;and, for every edgeuv2E, we haveu2V1andv2V2, or vice versa. That is, there are no edgesuvwithu;v2V1oru;v2V2. The setsV1andV2 are called thestable partsofG. If every vertex fromV1is adjacent to every vertex ofV2, we say that the graph iscomplete bipartiteand we denote it byKr;s, wherejV1j=rand jV2j=s. The graphK1;sis called astar graph.

2 Chapter 1. Graphs: basic concepts

Subgraphs

LetG= (V;E) be a graph.

The graphG0= (V0;E0) is asubgraph ofGifV0VandE0E. IfV0=V, it is called a spanning subgraphofG. LetSV,S6=;. The graphG[S] = (S;E0) withE0=fuv2E:u;v2Sgis called the subgraph induced (or spanned) by the set of verticesS.Graphs derived from a graph

Consider a graphG= (V;E).

ThecomplementofG, denoted byGc, is the graph with set of verticesVand set of edges E c=fuvjuv62Eg. A graph isomorphic to its complement is calledself-complementary. LetSV. The graph obtained bydeleting the verticesfromS, denoted byGS, is the graph having as vertices those ofVnSand as edges those ofGthat are not incident to any vertex fromS. In the case thatS=fvg, we denote itGv. LetSE. The graph obtained bydeleting the edgesfromS, denoted byGS, is the graph obtained fromGby removing all the edges fromS. That is,GS= (V;EnS). If

S=feg, we writeGe.

Letu;vbe vertices fromGthat are not adjacent. The graph obtained byadding the edge uvis the graphG+uv= (V;E[ fuvg).Operations with graphs

Consider two graphsG1= (V1;E1) andG2= (V2;E2).

Theunion ofG1andG2, denoted byG1[G2, is the graph that has as set of vertices V

1[V2and as set of edgesE1[E2.

Theproduct ofG1andG2, denoted byG1G2, is the graph that has as set of vertices V

1V2and whose adjacencies are given by

(u1;u2)(v1;v2),(u1v12E1andu2=v2) or (u1=v1andu2v22E2):

1.2. Exercises31.2 Exercises

1.1For each of the graphsNn,Kn,Pn,CnandWn, give:

1) a dra wingfor n= 4 andn= 6; 2) the adjacency matrix for n= 5; 3) the order, th esize, the maxim umdegree and the minim umdegree in terms of n.

1.2For each of the following statements, nd a graph with the required property, and give

its adjacency list and a drawing. 1)

A 3-regular graph of order at least 5.

2)

A bipartite gr aphof order 6.

3)

A complete bipartite graph of order 7.

4)

A star graph of order 7.

1.3Find out whether the complete graph, the path and the cycle of ordern1 are bipartite

and/or regular.

1.4Give the size:

1) of an r-regular graph of ordern; 2) of the complete bipartite graph Kr;s.

1.5LetV=fa;b;c;d;e;fg,E=fab;af;ad;be;de;efgandG= (V;E). Determine all the

subgraphs ofGof order 4 and size 4.

1.6The following ve items refer to the graphGdened as follows. The set of vertices

isV=f0;1;2;3;4;5;6;7;8g, and two verticesuandvare adjacent ifjuvj 2 f1;4;5;8g. Determine the order and the size of the following subgraphs ofG: 1)

The subgraph in ducedb yev env ertices.

2)

The subgraph in ducedb yo ddv ertices.

3)

The subgraph in ducedb ythe set f0;1;2;3;4g.

4) A spanning sub graphwith as man yedges as p ossiblebut without cycles.

1.7Consider the graphG= (V;E) withV=f1;2;3;4;5gandE=f12;13;23;24;34;45g.

Give the set of edges, the adjacency matrix and a drawing of the graphsGc,G4,G45 and

G+ 25.

4 Chapter 1. Graphs: basic concepts

1.8Consider a graphG= (V;E) of ordernand sizem. Letvbe a vertex andean edge of

G. Give the order and the size ofGc,GvandGe.

1.9Find out whether the complement of a regular graph is regular, and whether the comple-

ment of a bipartite graph is bipartite. If so, prove it; if not, give a counterexample.

1.10Give the set of edges and a drawing of the graphsK3[P3andK3P3, assuming that

the sets of vertices ofK3andP3are disjoint.

1.11Consider the graphsG1= (V1;E1) andG2= (V2;E2). Give the order, the degree of the

vertices and the size ofG1G2in terms of those ofG1andG2.

1.12Prove or disprove the following statements:

1)

If G1andG2are regular graphs, thenG1G2is regular.

2) If G1andG2are bipartite graphs, thenG1G2is bipartite.

1.13Draw all the graphs that haveV=fa;b;cgas set of vertices.

1.14Consider graphs whose set of vertices is [7] =f1;2;3;4;5;6;7g. Compute how many of

them are there ... 1) . ..withexactly 20 edges. 2) . ..intotal.

1.15For each of the following sequences, nd out if there is any graph of order 5 such that

the degrees of its vertices are given by that sequence. If so, give an example. 1)

3 ;3;2;2;2.

2)

4 ;4;3;2;1.3)4 ;3;3;2;2.

4)

3 ;3;3;2;2.5)3 ;3;3;3;2.

6)

5 ;3;2;2;2.

1.16Prove that if a graph is regular of odd degree, then it has even order.

1.17LetGbe a bipartite graph of ordernand regular of degreed1. Which is the size of

G? Could it be that the order ofGis odd?

1.18Prove that the size of a bipartite graph of ordernis at mostn2=4.

1.19LetGbe a graph with order 9 so that the degree of each vertex is either 5 or 6. Prove

that there are either at least 5 vertices of degree 6 or at least 6 vertices of degree 5.

1.20Alex and Leo are a couple, and they organize a party together with 4 other couples.

There are a number of greetings but, naturally, nobody says hello to their own partner. At the

1.2. Exercises5end of the party Alex asks everyone how many people did they greet, receiving nine dierent

answers. How many people did Alex greet and how many people did Leo greet? Hint:Describe a graph that models the situation. Find out how many people did each member of a couple greet.

1.21Determine, up to isomorphism, all the graphs of order four and size two.

1.22LetV=fa;b;c;dgandE=fab;ac;ad;dcg. Determine, up to isomorphism, all the

subgraphs of the graphG= (V;E).

1.23Classify by isomorphism type the graphs of Figure 1.1.

Figure 1.1:1G2G3G4

G 5G6G7

G9G8G10

G11G12G13

G1.24LetG= (V;E) andH= (W;B) be two graphs. Prove thatGandHare isomorphic if, and only if,GcandHcare isomorphic.

1.25Determine up to isomorphism the number of graphs of order 20 and size 188.

1.26A graph isself-complementaryif it is isomorphic to its complement. Prove that there

are no self-complementary graphs of order 3, but there are such graphs of order 4 and 5.

6 Chapter 1. Graphs: basic concepts

1.27A graph isself-complementaryif it is isomorphic to its complement.

1) Ho wman yedges d oesa self-complemen tarygraph of order nhave? 2) Pro vethat if nis the order of a self-complementary graph, thennis congruent with 0 or with 1 modulo 4. 3) Chec kthat for n= 4kwithk1, the following construction yields a self-complementary graph of ordern: let us takeV=V1[V2[V3[V4, where eachVicontainskvertices; the vertices ofV1andV2induce complete graphs; also, we have all edges betweenV1andV3, betweenV3andV4, and betweenV4andV2. 4) Ho wcould w emo difythe previous construction to build a self-co mplementarygraph of order 4k+ 1?

1.28LetGbe a graph of ordern6.

1) Sho wthat either GorGchas a vertexvof degree at least 3. 2) Pro vethat GorGccontains a cycle of length 3. (Consider the adjacencies between the neighbours of vertexvabove.) 3) Pro vethat at a meeting of at least 6 p eople,there are alw ays3 that m utuallykno weac h other, or 3 that mutually do not know each other. 2

Walks, connectivity and distance

2.1In each of the following graphs, nd paths of length 9 and 11, and cycles of length 5, 6,

8 and 9, if possible.1

2 3 4 51
6 91011
87
12 3 4 56
9 108
7G

2G2.2Prove that ifGis a graph of minimum degreed, thenGcontains a path of lengthd.

2.3A graph has order 13 and 3 connected components. Prove that one of the components

has at least 5 vertices.

2.4Use the algorithm DFS to nd out whether the following graphs, given by their adjacency

lists, are connected, and otherwise determine their connected components. Consider that the set of vertices is alphabetically ordered. 1) a b c d e f g h i jd d h a a a b c b b e g b d d i g g f i e j j f 2) a b c d e f g h i j k l mb a f b b c b b c a c g j d i h g e d k b i e k m g h j

8 Chapter 2. Walks, connectivity and distance

2.5Prove that if a graph has exactly two vertices of odd degree, then there is a path from

one of them to the other.

2.6LetGbe a graph of ordernthat has exactly two connected components, both of them

being complete graphs. Prove that the size ofGis at least (n22n)=4.

2.7LetGbe a graph of ordernwith exactlykconnected components. Prove that the size

ofGis larger than or equal tonk.

2.8LetGbe a graph of ordernwith exactlyk+1 connected components. In this exercise we

want to nd an upper bound for the size ofG. Toward this end, we dene an auxiliary graph Hof ordernthat hask+ 1 connected components:kcomponents are isomorphic toK1and one component is isomorphic toKnk. 1)

Compute the size of H.

2) Pro vethat the size of His larger than or equal to the size ofG.

2.9Find out all cut vertices and bridges of the following graphs.8

3 1 56
4 1 2

3GGG12213

4 56
72
3 4 5 6

72.10LetG= (V;E) be a connected graph of order at least 2. Takez62Vand deneG+z

as the graph that hasV[ fzgas set of vertices andE[ fzv:v2Vgas set of edges. Prove thatG+zhas no cut vertices.

2.11Find the smallestnfor which there is a 3-regular graph of ordernthat has a bridge.

2.12Prove that a 3-regular graph has a cut vertex if, and only if, it has some bridge.

2.13LetG= (V;E) be a graph andva vertex ofG. Prove:

1) if Gis not connected, thenGcis connected; 2) ( Gv)c=Gcv; 3) if Gis connected andvis a cut vertex ofG, thenvis not a cut vertex ofGc. 9

2.14Let us consider the graphs from exercise 2.4. Using the algorithm BFS, nd the distance

from the verticesaandbto each of the other vertices of the connected component to which they belong.

2.15Find the diameter of the following graphs.

1)Kn. 2)

Graphs of exercise 2.1. 3)Kr;s.

4)Cn.5)Wn.

6)Pn.

2.16For each of the following statements, give a connected graphG= (V;E) and a vertex

u2Vthat satises it.

1)D(G) =D(Gu).2) D(G)< D(Gu).3) D(G)> D(Gu).

Note:D(G) is the diameter ofG.

2.17 1) Find the eccen tricities,the radius, cen tralv erticesand cen terof: a) th egraphs from exercise 2.1; b)G= ([8];f12;14;15;23;34;38;46;47;56;67;78g). 2) Giv ean example of a connected graph w iththe same radi usand diameter. 3) Giv ean example of a connected graph w hosediameter is t wiceits radiu s.

2.18LetGbe a graph of order 1001 so that each vertex has degree500. Prove thatGhas

diameter2. 3

Eulerian and Hamiltonian graphs

3.1For each of the following graphs, either nd an Eulerian circuit or prove that there is not

one.G1G2G3G4 G5 G7G6G8G9G103.2Find out if the following gures can be drawn without lifting the pencil from the paper

and without repeating any line.3.3Determine the minimum number of times that one needs to lift the pencil from the paper

to draw each of the gures below without repeating any line.1)2) 11

3.4Find out for which values ofrandsthe complete bipartite graphKr;sis Eulerian.

3.5LetGbe a graph with exactly two connected components, both being Eulerian. Which

is the minimum number of edges that need to be added toGto obtain an Eulerian graph?

3.6Prove that a connected graph in which each vertex has even degree is bridgeless.

3.7Find out if it is possible to put all the pieces of a domino set in a row so that the when

two pieces are adjacent the values of the touching sides match, and moreover that the values at either end of the row also agree. If it is possible, give an explicit solution.

3.8Then-cubeis the graphQnwith set of verticesf0;1gnand where two vertices (x1;x2;:::;xn),

(y1;y2;:::;yn) are adjacent if they dier exactly in one coordinate. 1)

Dra wQifor 1i4.

2) Determine the order, the size and the degree sequence of Qn. 3)

Find for whic hv aluesof nthe graphQnis Eulerian.

3.9For each of the graphs from exercise 3.1, either nd a Hamiltonian cycle or prove that

there is none.

3.10Prove that if a bipartite graph is Hamiltonian, then the stable parts have the same

cardinal.

3.11Prove that a bipartite graphKr;sof order3 is Hamiltonian if, and only if,r=s.

3.12LetGbe a graph that has exactly two connected components, both of them Hamiltonian

graphs. Find the minimum number of edges that one needs to add toGto obtain a Hamiltonian graph.

3.13LetGbe a Hamiltonian graph that is not a cycle. Prove thatGhas at least 2 vertices

of degree3.

3.14Cameron and Robin have rented an apartment together. They throw a dinner party

where 10 other friends are invited. In the group of 12 people, each of them knows at least 6 other people. Prove that they can seat at a round table in such a way that everyone knows the two people sitting next to them. At the last minute another person arrives, who also knows at least 6 of the people present. Can you ensure now that they can still sit at the table following the previous condition?quotesdbs_dbs21.pdfusesText_27

[PDF] graph theory handwritten notes pdf

[PDF] graph theory problems and solutions

[PDF] graph theory questions and answers pdf

[PDF] graph theory theorems and proofs pdf

[PDF] graph theory with applications bondy murty solutions

[PDF] graph theory with applications bondy murty solutions pdf

[PDF] graph with 5 vertices of degrees 1

[PDF] graphème definition française

[PDF] graphic design courses in mumbai

[PDF] graphic design curriculum pdf

[PDF] graphic design for visually impaired

[PDF] graphic design manual principles and practice pdf

[PDF] graphic design notes

[PDF] graphic design pdf

[PDF] graphic design portfolio pdf 2019