![\"big-graph.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_159.jpg?resize=115%2C90\")
\nLet’s talk a bit about graphs, being a tad more formal about them.<\/p>\n
\nLet’s talk a bit about graphs, being a tad more formal about them.<\/p>\n
Let’s talk a bit about graphs, being a tad more formal about them.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-451","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7h","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/451","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=451"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/451\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=451"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nA graph G is a pair (V,E) where V is a non-empty set of *objects* called vertices, and E is a set of pairs of elements of V called edges<\/em> where a pair x={a,b} means that
\nvertices a and b are *adjacent*. We also say that edge x is *incident on* both a and b.
\nThe number of edges that are incident on a vertex is called the *degree* of a vertex.
\nTake any graph G, and take the sum of the degrees of all vertices. That number will
\nbe 2×|E| (2 times the cardinality of the set of edges.) This should be pretty obvious: since each edge has two ends, each edge adds to the degree of two different vertices.
\nAlready, we can show a moderately interesting fact. You *can’t* draw a graph with an odd number of vertices where the average degree of the vertices is three. It’s easy to prove: the number of edges in the graph is 1\/2 the sum of the degrees of the vertices. So for a graph with N vertices and average degree three, the sum of the degrees of all vertices is N×3. If N is odd, then N×3 is odd. But the sum of the degrees of all vertices *must* be even. Presto – can’t happen. (Typo corrected in this paragraph; 1\/2 was written 1\/3.)
\nOk, it’s trivial, but it’s cute. Moving on…
\n![\"iso.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_160.jpg?resize=216%2C102\")
\nWhat does equality mean in terms of graphs? We say two graphs are equivalent or *isomorphic* if and only if there is a one-to-one mapping between the vertices which preserves the adjacencies created by the edges. The shape of the graph doesn’t matter – just how the vertices are connected to one another. Another way of stating isomorphic equivalence is that two graphs are isomorphic if and only if you can re-arrange the vertices of one without<\/em> breaking any edges so that the two graphs are identical. So the two graphs to the right are isomorphic: one possible isomorphic map is (a→e), (b→f), (c→g), (d→h).
\n![\"noniso.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_161.jpg?resize=309%2C165\")
\nOn the other hand, you might think that the two graphs next to this paragraph are isomorphic – but you’d be wrong. There’s no way no rearrange the vertices to make these equivalent. It looks like as long as you map d to w and a to u that they’re isomorphic. But look more closely – a is adjacent to three vertices with degree 3 (b,c,e) and one with degree 4 (f); u is adjacent to 2 vertices with degree 3 (v,z) and two with degree 4 (w,y). There are no vertices in the left-hand graph adjacent to two vertices with degree 4.
\nAnd now, just to get them out of the way, here’s a bunch of definitions:
\n* Given two graphs, A=(V,E) and B=(W,F), B is a *subgraph* of A if and only if (W⊆V), and F⊆E. (You might think that we’d need to have an extra condition to say that the edges in F only include vertices in W; we don’t need to, because we said that (W,F) was a graph, which means that F only includes the vertices in W.)
\n![\"pentaplanar.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_162.jpg?resize=270%2C120\")
\n* If you can re-arrange a graph so that all if its edges can be draw without any of the edges crossing, then it’s called a *planar* graph. For example, if you look at first example to the right, you can see that the graph is planar – even though it is drawn with its edges crossing, it can be rearranged into the shape of the other, where no edges cross.
\n![\"fiveclique.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_163.jpg?resize=123%2C116\")
\n* If every vertex of a graph is adjacent to every other vertex, then the graph is called a clique. The graph to the right is a 5-clique – the clique with 5 vertices.
\n* If there is at least one path from any node to any other node, then the graph is *connected*.
\n* If there’s a path from any node in the graph back to itself, then the graph is cyclic.<\/p>\n","protected":false},"excerpt":{"rendered":"