MA3233 AY06-07 Sem 1

NATIONAL UNIVERSITY OF SINGAPOREMATHEMATICS SOCIETYPAST YEAR PAPER SOLUTIONSwith credits to Zheng ShaoxuanMA3233Algorithmic Graph TheoryAY2006/2007Sem1Question1(i).v1v2 v3 v4v5v6v7v8v9v10v11v12v13v14Tip:it is a good idea to count the cycles containing v10in a systemetic,categorised manner.One such way is to count the cycles via the cycle lengths.Furthermore,observe that the graph is bipartite since it admits a2-colouring.Hence,the only cycles that are possible within this graph are even cycles.By further observation we notice that there are no C12-s or C14-s possible in this graph of14vertices.Hence,we shall consider the four types of cycles:C4,C6,C8and C10.C4:v10v14v13v9v10,v10v12v11v9v10,v10v9v7v8v10.C6:v10v14v13v9v11v12v10,v10v14v13v9v7v8v10,v10v12v11v9v7v8v10,v10v9v7v5v6v8v10.C8:v10v14v13v9v7v5v6v8v10,v10v12v11v9v7v5v6v8v10,v10v9v7v5v1v2v6v8v10,v10v9v7v5v3v4v6v8v10.C10:v10v14v13v9v7v5v3v4v6v8v10,v10v14v13v9v7v5v1v2v6v8v10,v10v12v11v9v7v5v3v4v6v8v10,v10v12v11v9v7v5v1v2v6v8v10.(ii)As mentioned,G is bipartite and henceχ(G)=2.In particular,7of the14vertices of G has to be coloured‘1’and the other7is coloured‘2’(try it out!).For the graph H withχ(H)=2and witha maximum number of edges,H has to be a complete bipartite graph,and since G is a spanningsubgraph of H,H has two partite sets of7vertices each.Hence,by counting the number of edges in a complete bipartite graph as described,e(H)=7×7=49.(iii)Observe that,in particular,v1,v2,v3,and v4are vertices with degree2.As such,if G is hamiltonian, the edges v1v2,v2v6,v6v4,v4v3,v3v5,and v5v1must be in the resultant hamiltonian cycle since both edges incident to a vertex of degree2must be traversed.However,these6edges form a cycle by themselves,a contradiction!Hence G is not hamiltonian.(You can make a similar argument using v11,v12,v13and v14instead.)Wefind that1additional edge added to G is enough so that the resultant graph is hamiltonian,and hence the least number of new edges to be added to G is indeed1.One such edge is v1v12(there are other similar examples),and the resultant graph and hamiltonian cycle is as shown below:v1v2 v3 v4v5v6v7v8v9v10v11v12v13v14(iv)An eulerian graph is one that has all vertices with even degree.In the original G,only2vertices, v7and v8has odd degree;the rest have even degree.These two vertices are adjacent.For G to be eulerian alone,we can add one edge from v7to v8.However,the resultant graph becomesa multigraph which is not wanted.Hence one edge is not enough to satisfy the requirements asstated in the question.Consider adding two edges.To get rid of the odd degrees of v7and v8,and not to convert any other vertices to have odd degree,one edge must be incident to v7,one to v8,and both these edges must be incident to the same vertex at the other end.By symmetry we consider this other vertex to be only either v1or v5.If this vertex is v5,then the resultant graph becomes a multigraph which is not wanted.If this vertex is v1,then by a similar argument in(1iii)the graph is not hamiltonian (there exists certain edges which must be included in the hamiltonian cycle,which forms a cycle by itself).Hence two edges is not sufficient to satisfy the requirements as stated in the question.Three edges is sufficient to do so,and hence three is the least number of new edges to be added.One way to do so(again there are other ways)is the addition of v1v7,v8v12and v1v12.The resultant graph,with all vertices of even degree,and the hamiltonian cycle is shown below:v1v2 v3 v4v5v6v7v8v9v10v11v12v13v14(v)A spanning tree of G with greatest possible number of cut-vertices is one which has least number of end-vertices.If possible,we try to construct a path which is a spanning tree of G as a path has only2end-vertices,the least possible in any non-trivial graph.Wefind that a spanning path is possible!Since we only require1additional edge in G to form a hamiltonian cycle,there already exists a hamiltonian/spanning path in G.Hence we use the same spanning path as discovered earlier in(1iii)as our desired spanning tree,minus the extra edge v1v12,as shown belowv 1v 2v 3v 4v 5v 6v 7v 8v 9v 10v 11v 12v 13v 14Question 2Define thefollowing graphs as follow:GG 1G 2By considering the removal of the highlighted edge of G ,τ(G )=τ(G 1)+τ(G 2).Hence it suffices to find the number of spanning trees of the two latter graphs.τ(G 2)can be (relatively)easily calculated with the mentioned edge removal method andsome simple manipulation as taught in MA3233.Define the following graphs as such:G 3G 4G5G6G7By considering two identical graphs sharing one single vertex,τ(G2)=(τ(G3))2.By considering the removal of the highlighted edge in G3,τ(G3)=τ(G4)+τ(G5).The highlighted edge in G4 makes no difference to the count of the number of spanning trees,henceτ(G4)=τ(G6).By considering two C3s sharing a common edge,τ(G6)=3×3−1=8.By considering the removal of the highlighted edge of G5,τ(G5)=τ(G6)+τ(G7).By considering two C2s(multigraph)sharing a single vertex,τ(G7)=2×2=4.Therefore,τ(G5)=8+4=12,τ(G4)=8,τ(G3)=8+12=20,and henceτ(G2)=202=400.You may attempt using a similar method tofindτ(G1)andfinally end up with an answer of320, but be warned that the process is extremely tedious and time consuming for this case.Owing to the symmetric nature of the graph,we may attempt using a combinatorial method tofindτ(G1) instead.Recolour the edges of G1as such:G1To count the number of spanning trees of G1,consider the3different and mutually exclusive types of spanning trees possible:(i)where both of the bolded black edges are within the spanning tree; (ii)where exactly one of the bolded black edges is within the spanning tree;(iii)where both the bolded black edges are NOT within the spanning tree.For(i),exactly5edges needs to be removed to form a spanning tree,one from each colour pair as well as one of the four uncoloured and unbolded edges.The number of ways to choose these5 edges is2×2×2×2×4=64.For(ii),wefirst realise there are2ways to choose which of the bolded black edges is to be removed. By symmetry,we only need to consider that the left bolded black edge is removed.4more edges needs to be removed after this:one from the green pair and one from the red pair.For the2 remaining edges to be removed to break all cycles in the graph,we could either do it by removing one from the blue pair and one from the yellow pair,or we could do it by removing one from the uncoloured unbolded edges and one from any of the blue or yellow edges.Hence,the number of ways to choose these edges to form a spanning tree is2(2×2)(2×2+4×4)=160.For (iii),after removing the 2black edges,we need to remove 3more edges such that all cycles are broken.One way to do so is to choose 3out of the 4colours,and remove 1edge from each of the 3colour pairs.The other way is to first remove 1of the 4unbolded uncoloured edges,then remove 1out of the 4blue or yellow edges to break the blue-yellow C 4as well as 1out of the 4green or red edges to break the green-red C 4.Take note that removing 2or more of the unbolded uncoloured edges disconnects the graph and hence we do not consider the cases for doing so.Hence,the number of ways to choose these edges to form a spanning tree is 43 ×2×2×2+4×4×4=96.By summing the results of the three cases,τ(G 1)=64+160+96=320.Therefore,the number of spanning trees of G ,τ(G )=320+400=720.Question 3v 1v 2v 3v 4v 5v 67v 8139451214596114549Apply Edmond’s algorithm to the above graph:There are 4odd vertices in the graph,v 1,v 2,v 3and v 4.The least weight and path of least weight between each pair of these vertices are:•v 1−v 2:13(via v 1v 2),•v 1−v 3:18(via v 1v 5v 6v 3),•v 1−v 4:15(via v 1v 5v 4),•v 2−v 3:14(via v 2v 7v 3),•v 2−v 4:19(via v 2v 7v 6v 5v 4),•v 3−v 4:14(via v 3v 4).The weights of the 3possible pairings between these 4vertices are:•v 1−v 2and v 3−v 4:13+14=27,•v 1−v 3and v 2−v 4:18+19=37,•v 1−v 4and v 2−v 3:15+14=29.The minimum weight pairing is v 1−v 2and v 3−v 4.We append the paths of least weights of the two paths within the minimum weight pairing into the original graph.We obtain:v 1v 2v 3v 4v 5v 6v 7v 81394512145961145491314Using Fluerry’s algorithm,we construct a closed trail of this new graph which contains all its edges.One such trail can be v 1v 2v 1v 8v 2v 7v 8v 5v 4v 3v 4v 6v 3v 7v 6v 5v 1,and this is also the closed walk with minimum weight which contains all the edges in the original graph.(there are many other possible answers).The weight of our closed walk is (27)+(5+4+9+6+11+4+12+13+9+5+4+14+9+5)=137.Question 4Apply Dijkstra’s algorithm to the graph as drawn in the question.We begin with this table listing the shortest distances from u 9to each of the other vertices,as well as the previous vertex on the path of shortest distance as will be determined when performing the algorithm.Vertexu 1u 2u 3u 4u 5u 6u 7u 8u 9Current shortest distance from u 9∞∞∞∞∞∞∞∞0Previous vertex on path of shortest distance --------NA Is it the fixed shortest possible distance?--------YFocus on u 9,having shortest distance of 0from u 9.u 6,u 7and u 8are unfixed vertices adjacent to u 9.Path u 6−u 9passing through u 6u 9has distance of 4+0=4,which is smaller than its current value of ∞.Path u 7−u 9passing through u 7u 9has distance of 5+0=5,which is smaller than its current value of ∞.Path u 8−u 9passing through u 8u 9has distance of 3+0=3,which is smaller than its current value of ∞.Hence update table on new shortest distances from u 9,of u 6,u 7and u 8:Vertexu 1u 2u 3u 4u 5u 6u 7u 8u 9Current shortest distance from u 9∞∞∞∞∞4530Previous vertex on path of shortest distance -----u 9u 9u 9NA Is it the fixed shortest possible distance?--------Y Among the unfixed shortest distances,u 8has the shortest distance of 3from u 9.Hence fix u 8.Vertexu 1u 2u 3u 4u 5u 6u 7u 8u 9Current shortest distance from u 9∞∞∞∞∞4530Previous vertex on path of shortest distance -----u 9u 9u 9NA Is it the fixed shortest possible distance?-------YYFocus on u 8,having shortest distance of 3from u 9.u 4,u 6and u 7are unfixed vertices adjacent to u 8.Path u 4−u 9passing through u 4u 8has distance of 7+3=10,which is smaller than its currentvalue of∞.Path u6−u9passing through u6u8has distance of2+3=5,which is larger than its current value of4.Path u7−u9passing through u7u8has distance of6+3=9,which is larger than its current value of5.Hence update table on new shortest distances from u9,of u4:Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9∞∞∞10∞4530 Previous vertex on path of shortest distance---u8-u9u9u9NAIs it thefixed shortest possible distance?-------Y Y Among the unfixed shortest distances,u6has the shortest distance of4from u9.Hencefix u6.Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9∞∞∞10∞4530 Previous vertex on path of shortest distance---u8-u9u9u9NAIs it thefixed shortest possible distance?-----Y-Y YFocus on u6,having shortest distance of4from u9.u4and u5are unfixed vertices adjacent to u6. Path u4−u9passing through u4u6has distance of4+4=8,which is smaller than its current value of10.Path u5−u9passing through u5u6has distance of3+4=7,which is smaller than its current value of∞.Hence update table on new shortest distances from u9,of u4and u5:Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9∞∞∞874530 Previous vertex on path of shortest distance---u6u6u9u9u9NAIs it thefixed shortest possible distance?-----Y-Y Y Among the unfixed shortest distances,u7has the shortest distance of5from u9.Hencefix u7.Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9∞∞∞874530 Previous vertex on path of shortest distance---u6u6u9u9u9NAIs it thefixed shortest possible distance?-----Y Y Y YFocus on u7,having shortest distance of5from u9.u3and u4are unfixed vertices adjacent to u7. Path u3−u9passing through u3u7has distance of5+5=10,which is smaller than its current value of∞.Path u4−u9passing through u4u7has distance of4+5=9,which is larger than its current value of8.Hence update table on new shortest distances from u9,of u3:Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9∞∞10874530 Previous vertex on path of shortest distance--u7u6u6u9u9u9NAIs it thefixed shortest possible distance?-----Y Y Y Y Among the unfixed shortest distances,u5has the shortest distance of7from u9.Hencefix u5.Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9∞∞10874530 Previous vertex on path of shortest distance--u7u6u6u9u9u9NAIs it thefixed shortest possible distance?----Y Y Y Y YFocus on u5,having shortest distance of7from u9.u1,u2and u4are unfixed vertices adjacent to u5.Path u1−u9passing through u1u5has distance of3+7=10,which is smaller than its current value of∞.Path u2−u9passing through u2u5has distance of7+7=14,which is smaller than its current value of∞.Path u4−u9passing through u4u5has distance of9+7=16,which is larger than its current value of8.Hence update table on new shortest distances from u9,of u1and u2: Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9101410874530 Previous vertex on path of shortest distance u5u5u7u6u6u9u9u9NAIs it thefixed shortest possible distance?----Y Y Y Y Y Among the unfixed shortest distances,u4has the shortest distance of8from u9.Hencefix u4.Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9101410874530 Previous vertex on path of shortest distance u5u5u7u6u6u9u9u9NAIs it thefixed shortest possible distance?---Y Y Y Y Y Y Focus on u4,having shortest distance of8from u9.u2and u3are unfixed vertices adjacent to u4.Path u2−u9passing through u2u4has distance of6+8=14,which is equal than its current value of14.Path u3−u9passing through u3u4has distance of9+8=17,which is larger than its current value of10.Hence there is no update of the table in this step.Among the unfixed shortest distances,u1has the shortest distance of10from u9(alternatively we can choose u3which also has a distance of10).Hencefix u1.Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9101410874530 Previous vertex on path of shortest distance u5u5u7u6u6u9u9u9NAIs it thefixed shortest possible distance?Y--Y Y Y Y Y Y Focus on u1,having shortest distance of10from u9.u2and u3are unfixed vertices adjacent to u1.Path u2−u9passing through u2u1has distance of4+10=14,which is equal than its current value of14.Path u3−u9passing through u3u1has distance of13+10=13,which is larger than its current value of10.Hence there is no update of the table in this step.Among the unfixed shortest distances,u3has the shortest distance of10from u9.Hencefix u3.Vertex u1u2u3u4u5u6u7u8u9 Current shortest distance from u9101410874530 Previous vertex on path of shortest distance u5u5u7u6u6u9u9u9NAIs it thefixed shortest possible distance?Y-Y Y Y Y Y Y Y Focus on u3,having shortest distance of10from u9.u2is the unfixed vertex adjacent to u3.Path u2−u9passing through u2u3has distance of8+10=18,which is larger than its current value of14.Hence there is no update of the table in this step.Only u2is unfixed at this point.Hencefix u2.We now have ourfinal table,which shows the shortest distances from u9to all the vertices in G:Vertex u1u2u3u4u5u6u7u8u9Shortest distance from u9101410874530Question5(i)This graph is hamiltonian.The hamiltonian cycle is as shown below,where the blue edges indicateedges that have to be included due to vertices having only two possible adjacent edges left that could be in the hamiltonian cycle,red crosses represent edges that are not possible to be in the hamiltonian cycle due to similar logical deductions,and green edges represents the rest of the edges filled in to complete the hamiltonian cycle(your own hamiltonian cycle can have different such green edges,as long as all vertices are in the cycle).v 1v 2v 3v 4v 5v 6v 7v 8v 9v 10v 11v 12v 13v 14v 15v 16v 17v 18v 19v 20v 21v 22v 23v 24v 25w 1w 2w 3w 4w 5X X X XXX XXXXX XX XXX X (ii)Consider the following construction,where the blue edges indicate edges that have to be includeddue to vertices having only two possible adjacent edges left that could be in the hamiltonian cycle,and red crosses represent edges that are not possible to be in the hamiltonian cycle due to similar logical deductions.v 1v 2v 3v 4v 5v 6v 7v 8v 9v 10v 11v 12v 13v 14v 15v 16v 17v 18v 19v 20v 21v 22v 23v 2425w 1w 2w 3w 4w 5X X X XXX XX X X X X X XXX XSuppose a hamiltonian cycle exists for this graph.We claim that either v 22v 18or v 22v 17is in the hamiltonian cycle.Suppose not.Then both v 22v 18and v 22v 17are not in the hamiltonian cycle.Hence v 17v 18is in the hamiltonian cycle.Then v 11v 17is not in the hamiltonian cycle otherwise a C 4is formed.Then both v 10v 11and v 10v 17are in the hamiltonian cycle.But this forms a C 5:v 10v 11w 3v 18v 17v 10!A contradiction.With this claim,v 22v 23and v 22v 25are both not in the hamiltonian cycle.Hence,v 25v 23,v 23v 24and v 25v 24are all in the hamiltonian cycle,thus forming a C 3!A contradiction.Hence this graph is not hamiltonian.Question6Consider a graph G.Let people be represented by vertices,and the symmetric relation‘knowing’between two people be represented by an edge between the two respective vertices.The given condition translates as:G has n vertices where n≥4.∀distinct u,v,w∈V(G),if uw/∈E(G), then vw∈E(G)(otherwise w is a‘person’that neither u or v knows).The question asks to prove that G is hamiltonian.If G is a complete graph then it is straightforward that G is hamiltonian.Consider G to be not a complete graph.There exists distinct u,v∈V(G)such that uv/∈E(G).We claim that ∀w∈V(G)\{u,v},uw∈E(G)and vw∈E(G).Suppose not.Then∃w∈V(G)\{u,v}such that,without loss of generality,uw/∈E(G).But now consider w and v:uw/∈E(G)and uv/∈E(G),violating the given condition!A contradiction.Hence the claim is true.Hence,for all distinct non-adjacent x,y∈V(G),d(x)=n−2and d(y)=n−2.Hence d(x)+d(y)= 2n−4>n for n≥4.Therefore,by Ore’s Theorem,G is hamiltonian.Question7(i)Note:This question requires a resolution to the girth of graphs without any cycles,e.g.trees.It isgenerally considered that a tree has infinite girth.If a tree is considered to be a graph with‘girth at least6’,then simple counter examples to the statement exists,such as:The graph above has a disconnected complement and hence is not hamiltonian.We shall now only consider graphs withfinite girths,i.e.,graphs which contains cycles.Given G,a graph with cycles with girth at least6,consider any adjacent vertices x and y in G.Let N(x)be the set of vertices adjacent to x,N(y)be the set of vertices adjacent to y and S be the set of vertices adjacent to neither x or y.No vertex falls in both N(x)and N(y),or else for any such vertex w,xwyx is a C3,a contradiction to the girth requirement.Also,no pairs of vertices in N(x)are adjacent,otherwise for any such a pair of vertices u and v,xuvx is a C3,another contradiction.By a similar argument no pairs of vertices in N(y)are adjacent.Also,no vertex in N(x)is adjacent with vertices in N(y),otherwise for any such a pair of vertices u∈N(x)and v∈N(y),xuvyx is a C4,another contradiction.We claim that|S|≥2.Suppose not.If|S|=0,then G has no cycles,which is what we did not want.If|S|=1,let the only vertex in S be z.z is adjacent to at most one vertex in N(x), otherwise for two vertices u,v∈N(x)that z is adjacent to,xuzv is a C4,a contradiction.By a similar argument z is adjacent to at move one vertex in N(y).If z is not adjacent to all vertices in N(x),or not adjacent to all vertices in N(y),then G has no cycles by considering all previous conditions.Hence z is adjacent to exactly one vertex in N(x),p,and exactly one vertex in N(y), q.But xpzqyx is a C5,another contradiction!Hence|S|≥2.Consider G.x and y are non-adjacent vertices in G.In G,d(x)=|N(y)|+|S|,and d(y)= |N(x)|+|S|.Hence d(x)+d(y)=|N(x)|+|N(y)|+|S|+|S|≥|N(x)|+|N(y)|+|S|+2=v(G)=v(G).This holds for any non-adjacent x and y in G.Hence by Ore’s Theorem,G is hamiltonian.(ii)Suppose G is disconnected.Consider the vertex v∈G where d(v)=∆(G)= n2.There existsn− n2−1=n2−1vertices in G not adjacent to v.Let the set of these vertices be S.Since G is assumed to be disconnected,there exists a vertex w in S such that v and w are in different components of G,otherwise all vertices in G are in the same component as v and theMA3233Algorithmic Graph Theory AY2006/2007Sem1 graph is connected.Hence,w is not adjacent to any vertices in G\S.Hence w can only be adjacentto vertices in S. Hence,d(w)<|S|= n2−1=δ(G),a contradiction!Therefore G is connected.(iii)Since n≡1(mod4),the number of vertices in G is paring G and G,all corresponding vertices u∈V(G)and u ∈V(G)can be paired up such that d(u)+d(u )=n−1.Since G is self complementary,G∼=G.Suppose there is no vertex with degree n−12.∀u∈V(G),∃distinct v∈V(G)such that d(u)+d(v)=n−1(distinct since their degrees would not be thesame).Since there are an odd number of vertices,we can form up n−12disjoint pairs of verticeswith degree sums of n−1,with one vertex left over.Call this leftover vertex x.The degree of x is the sum of total degrees of all vertices in G,subtracted by n−12pairs of(n−1).Hence,d(x)= n2−(n−1)n−12=12(n(n−1)−(n−1)(n−1))=n−12,a contradiction!Hence thereexists a vertex with degree n−12.NUS Math LaTeXify Proj Team Page:11of11NUS Mathematics Society。