{"id":160340,"date":"2023-09-26T13:10:21","date_gmt":"2023-09-26T07:40:21","guid":{"rendered":"https:\/\/www.gkseries.com\/blog\/?p=160340"},"modified":"2023-09-26T13:10:22","modified_gmt":"2023-09-26T07:40:22","slug":"let-g-be-a-graph-with-100-vertices-with-each-vertex-labelled-by-a-distinct-permutation-of-the-numbers-12-100","status":"publish","type":"post","link":"https:\/\/www.gkseries.com\/blog\/let-g-be-a-graph-with-100-vertices-with-each-vertex-labelled-by-a-distinct-permutation-of-the-numbers-12-100\/","title":{"rendered":"Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, \u2026 , 100"},"content":{"rendered":"\n

Q. Let G <\/em>be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, \u2026 , 100. There is an edge between vertices \ud835\udc62 and \ud835\udc63 if and only if the label of \ud835\udc62 can be obtained by swapping two adjacent numbers in the label of \ud835\udc63. Let \ud835\udc66 denote the degree of a vertex in G<\/em>, and \ud835\udc67 denote the number of connected components in G<\/em>. Then, \ud835\udc66 + 10\ud835\udc67 =\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/p>\n\n\n\n

.Ans: 109<\/p>\n\n\n\n

Sol:<\/p>\n\n\n\n

There is an edge between vertices u and v if the label of u can be obtained by swapping two adjacent numbers in the label of v.\u00a0
Then the set of swapping numbers will be {(1, 2), (2, 3), \u2026\u2026\u2026..(9, 9)}\u00a0
There will be 99 such sets, i.e. number of edges = 99\u00a0
and each vertex will have 99 edges corresponding to it. \u00a0<\/p>\n\n\n\n

Say graph with 3! vertices, then vertices will be like {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}\u2026 Let\\\u2019s pick vertex {123}, degree will be 2 since it will be connected with two other vertices {213} and {132}.<\/p>\n\n\n\n

We can conclude that for n, degree will be n-1.<\/p>\n\n\n\n

SO, degree of each vertex = 99 (as said y)\u00a0
As the vertices are connected together, the number of connected components formed will be 1 (as said z).<\/p>\n\n\n\n

y+10z = 99+10(1) = 109<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"

Q. Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, \u2026 , 100. There is an edge between vertices \ud835\udc62 and \ud835\udc63 if and only if the label of \ud835\udc62 can be obtained by swapping two adjacent numbers in the label of \ud835\udc63. Let […]<\/p>\n","protected":false},"author":419,"featured_media":160341,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[5141],"tags":[5140],"class_list":["post-160340","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-gate","tag-gate-questions"],"_links":{"self":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160340","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/users\/419"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/comments?post=160340"}],"version-history":[{"count":1,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160340\/revisions"}],"predecessor-version":[{"id":160342,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160340\/revisions\/160342"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media\/160341"}],"wp:attachment":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media?parent=160340"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/categories?post=160340"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/tags?post=160340"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}