Mathematics 1 Part I: Graph Theory

1 Bachelor Degree in Informatics EngineeringFacultat d Inform`atica de BarcelonaMathematics 1 Part I: Graph TheoryExercises and problemsFebruary 2019 Departament de Matem`atiquesUniversitat Polit`ecnica de CatalunyaThe 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 yearsby the members of the Departament de Matem`atica Aplicada 2. Other exercises came from thebibliography of the course or from other texts, and some of them were new. Since Mathematics1 was first taught in 2010 several problems have been modified or rewritten by the professorsinvolved in the teaching of the would like to acknowledge the assistance of the scholar Gabriel Bernardino in the writingof the by Anna de Mier and the scholar Bernat problem list has been revised during the academic year 2018 Graphs: basic Types of graphs. Subgraphs. Operations with.

2 Exercises..32 Walks, connectivity and distance73 Eulerian and Hamiltonian graphs104 Trees12 Review exercises151 Graphs: basic Types of graphs. Subgraphs. Operations with following are some important families of graphs that we will use often. Letnbe a positiveinteger andV={x1, x2, .. , xn}.Thenull graphof ordern, denoted byNn, is the Graph of ordernand size 0. The graphN1is called thetrivial graphof ordern, denoted byKn, is the Graph of ordernthat has all possibleedges. We observe thatK1is a trivial Graph graphof ordern, denoted byPn= (V, E), is the Graph that has as a set of edgesE={x1x2, x2x3, .. , xn 1xn}.Thecycle graphof ordern 3, denoted byCn= (V, E), is the Graph that has as a set ofedgesE={x1x2, x2x3, .. , xn 1xn, xnx1}.Thewheel graphof ordern 4, denoted byWn= (V, E), is the Graph that has as a setof edgesE={x1x2, x2x3, .. , xn 1x1} {xnx1, xnx2, .. , xnxn 1}.Letrandsbe positive Graph isr-regularif all vertices have graphG= (V, E) isbipartiteif there are two non-empty subsetsV1andV2such thatV=V1 V2,V1 V2= and, for every edgeuv E, we haveu V1andv V2, orvice versa.

3 That is, there are no edgesuvwithu, v V1oru, v V2. The setsV1andV2are called thestable partsofG. If every vertex fromV1is adjacent to every vertex ofV2,we say that the Graph iscomplete bipartiteand we denote it byKr,s, where|V1|=rand|V2|=s. The graphK1,sis called astar 1. Graphs: basic conceptsSubgraphsLetG= (V, E) be a graphG = (V , E ) is asubgraph ofGifV VandE E. IfV =V, it is calleda spanning V,S6= . The graphG[S] = (S, E ) withE ={uv E:u, v S}is called thesubgraph induced (or spanned) by the set of derived from a graphConsider a graphG= (V, E).ThecomplementofG, denoted byGc, is the Graph with set of verticesVand set of edgesEc={uv|uv6 E}. A Graph isomorphic to its complement is V. The Graph obtained bydeleting the verticesfromS, denoted byG S, is thegraph having as vertices those ofV\Sand as edges those ofGthat are not incident toany vertex fromS. In the case thatS={v}, we denote itG E. The Graph obtained bydeleting the edgesfromS, denoted byG S, is thegraph obtained fromGby removing all the edges fromS.

4 That is,G S= (V, E\S). IfS={e}, we writeG , vbe vertices fromGthat are not adjacent. The Graph obtained byadding the edgeuvis the graphG+uv= (V, E {uv}).Operations with graphsConsider two graphsG1= (V1, E1) andG2= (V2, E2).Theunion ofG1andG2, denoted byG1 G2, is the Graph that has as set of verticesV1 V2and as set of edgesE1 ofG1andG2, denoted byG1 G2, is the Graph that has as set of verticesV1 V2and whose adjacencies are given by(u1, u2) (v1, v2) (u1v1 E1andu2=v2) or (u1=v1andu2v2 E2). each of the graphsNn,Kn,Pn,CnandWn, give:1) a drawing forn= 4 andn= 6;2) the adjacency matrix forn= 5;3) the order, the size, the maximum degree and the minimum degree in terms each of the following statements, find a Graph with the required property, and giveits adjacency list and a ) A 3-regular Graph of order at least ) A bipartite Graph of order ) A complete bipartite Graph of order ) A star Graph of order out whether the complete Graph , the path and the cycle of ordern 1 are bipartiteand/or the size:1) of anr-regular Graph of ordern;2) of the complete bipartite graphKr, {a, b, c, d, e, f},E={ab, af, ad, be, de, ef}andG= (V, E).

5 Determine all thesubgraphs ofGof order 4 and size following five items refer to the graphGdefined as follows. The set of verticesisV={0,1,2,3,4,5,6,7,8}, and two verticesuandvare adjacent if|u v| {1,4,5,8}.Determine the order and the size of the following subgraphs ofG:1) The subgraph induced by even ) The subgraph induced by odd ) The subgraph induced by the set{0,1,2,3,4}.4) A spanning subgraph with as many edges as possible but without the graphG= (V, E) withV={1,2,3,4,5}andE={12,13,23,24,34,45 }.Give the set of edges, the incidence and adjacency matrices, and a drawing of the graphsGc,G 4,G 45 andG+ 1. Graphs: basic a graphG= (V, E) of ordernand sizem. Letvbe a vertex andean edge ofG. Give the order and the size ofGc,G vandG 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 the set of edges and a drawing of the graphsK3 P3andK3 P3, assuming thatthe sets of vertices ofK3andP3are the graphsG1= (V1, E1) andG2= (V2, E2).

6 Give the order, the degree of thevertices and the size ofG1 G2in terms of those or disprove the following statements:1) IfG1andG2are regular graphs, thenG1 G2is ) IfG1andG2are bipartite graphs, thenG1 G2is all the graphs that haveV={a, b, c}as set of graphs whose set of vertices is [7] ={1,2,3,4,5,6,7}. Compute how many ofthem are there ..1) .. with exactly 20 ) .. with exactly 16 ) .. in each of the following sequences, find out if there is any Graph of order 5 such thatthe degrees of its vertices are given by that sequence. If so, give an ) 3,3,2,2, ) 4,4,3,2, ) 4,3,3,2, ) 3,3,3,2, ) 3,3,3,3, ) 5,3,2,2, that if a Graph is regular of odd degree, then it has even a bipartite Graph of ordernand regular of degreed 1. Which is the size ofG? Could it be that the order ofGis odd? that the size of a bipartite Graph of ordernis at mostn2 a Graph with order 9 so that the degree of each vertex is either 5 or 6. Provethat there are either at least 5 vertices of degree 6 or at least 6 vertices of degree and Leo are a couple, and they organize a party together with 4 other are a number of greetings but, naturally, nobody says hello to their own partner.

7 At theend of the party Alex asks everyone how many people did they greet, receiving nine differentanswers. 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 memberof a couple , up to isomorphism, all the graphs of order four and size {a, b, c, d}andE={ab, ac, ad, dc}. Determine, up to isomorphism, all thesubgraphs of the graphG= (V, E). by isomorphism type the graphs of Figure (V, E) andH= (W, B) be two graphs. Prove thatGandHare isomorphic if,and only if,GcandHcare up to isomorphism the number of graphs of order 20 and size 1. Graphs: basic Graph isself-complementaryif it is isomorphic to its complement. Prove that thereare no self-complementary graphs of order 3, but there are such graphs of order 4 and Graph isself-complementaryif it is isomorphic to its ) How many edges does a self-complementary Graph of ordernhave?2) Prove that ifnis the order of a self-complementary Graph , thennis congruent with 0 orwith 1 modulo ) Check that forn= 4kwithk 1, the following construction yields a self-complementarygraph of ordern: let us takeV=V1 V2 V3 V4, where eachVicontainskvertices; thevertices ofV1andV2induce complete graphs; also, we have all edges betweenV1andV3,betweenV3andV4, and ) How could we modify the previous construction to build a self-complementary Graph oforder 4k+ 1?

8 A Graph of ordern ) Show that eitherGorGchas a vertexvof degree at least ) Prove thatGorGccontains a cycle of length 3. (Consider the adjacencies between theneighbours of vertexvabove.)3) Prove that at a meeting of at least 6 people, there are always 3 that mutually know eachother, or 3 that mutually do not know each , connectivity and each of the following graphs, find paths of length 9 and 11, and cycles of length 5, 6,8 and 9, if that ifGis a Graph of minimum degreed, thenGcontains a path of Graph has order 13 and 3 connected components. Prove that one of the componentshas at least 5 the algorithm DFS to find out whether the following graphs, given by their adjacencylists, are connected, and otherwise determine their connected components. Consider that theset of vertices is alphabetically )abcdefghijddhaaabcbbegbddiggfiejjf2)abc defghijklmbafbbcbbcacgjdihgedkbiekmghj8 Chapter 2. Walks, connectivity and that if a Graph has exactly two vertices of odd degree, then there is a path fromone of them to the a Graph of ordernthat has exactly two connected components, both of thembeing complete graphs.

9 Prove that the size ofGis at least (n2 2n) a Graph of ordernwith exactlykconnected components. Prove that the sizeofGis larger than or equal ton a Graph of ordernwith exactlyk+ 1 connected components. In this exercise wewant to find an upper bound for the size ofG. Toward this end, we define an auxiliary graphHof ordernthat hask+ 1 connected components:kcomponents are isomorphic toK1andone component is isomorphic toKn ) Compute the size ) Prove that the size ofHis larger than or equal to the size that a 3-regular Graph has a cut vertex if, and only if, it has some the smallestnfor which there is a 3-regular Graph of ordernthat has a (V, E) be a connected Graph of order at least 2. Takez6 Vand defineG+zas the Graph that hasV {z}as set of vertices andE {zv:v V}as set of edges. ProvethatG+zis (V, E) be a Graph andva vertex ofG. Prove:1) ifGis not connected, thenGcis connected;2) (G v)c=Gc v;3) ifGis connected andvis a cut vertex ofG, thenvis not a cut vertex out whether any of the following graphs is us consider the graphs from exercise Using the algorithm BFS, find the distancefrom the verticesaandbto each of the other vertices of the connected component to whichthey the diameter of the following ) ) Graphs of exercise )Kr, ) ) ) each of the following statements, give a connected graphG= (V, E) and a vertexu Vthat satisfies )D(G) =D(G u).

10 2)D(G)< D(G u).3)D(G)> D(G u).Note:D(G) is the diameter (V, E) be a connected Graph andv V. Let us introduce the following concepts:ITheeccentricity of the vertexv,e(v), is the maximum of the distances fromvto any othervertex of the Graph , that is,e(v) = max{d(v, x) :x V}.ITheradius ofG,r(G), is the minimum of the eccentricities of the vertices ofG, that is,r(G) = min{e(v) :v V}.IAcentral vertex ofGis a vertexusuch thate(u) =r(G).Answer the following ) Find the eccentricities, the radius and the central vertices of: a) the graphs from ; b)G= ([8],{12,14,15,23,34,38,46,47,56,67,78}) .2) Give an example of a Graph with the same radius and ) Give an example of a Graph whose diameter is twice its ) Prove that, for each graphG,r(G) D(G) 2r(G), whereD(G) is the diameter a Graph of order 1001 so that each vertex has degree 500. Prove thatGhasdiameter and Hamiltonian each of the following graphs, either find an Eulerian circuit or prove that there is out if the following figures can be drawn without lifting the pencil from the paperand without repeating any the minimum number of times that one needs to lift the pencil from the paperto draw each of the figures below without repeating any )1) out for which values ofrandsthe complete bipartite graphKr,sis a Graph with exactly two connected components, both being Eulerian.