{"id":459,"date":"2007-07-02T21:49:09","date_gmt":"2007-07-02T21:49:09","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/07\/02\/a-taxonomy-of-some-basic-graphs\/"},"modified":"2007-07-02T21:49:09","modified_gmt":"2007-07-02T21:49:09","slug":"a-taxonomy-of-some-basic-graphs","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/07\/02\/a-taxonomy-of-some-basic-graphs\/","title":{"rendered":"A Taxonomy of Some Basic Graphs"},"content":{"rendered":"

Naming Some Special Graphs
\nWhen we talk about graph theory – particularly when we get to some of the
\ninteresting theorems – we end up referencing certain common graphs or type of graphs
\nby name. In my last post, I had to work in the definition of snark, and struggle around
\nto avoid mentioning another one, so it seems like as good a time as any to run through
\nsome of the basics. This won’t be an exciting post, but you’ve got to do the definitions sometime. And there’s a bunch of pretty pictures, and even an interesting simple proof or two.<\/p>\n


\n&uot\"k6.jpg\"
\nA *complete* graph is a graph where every vertex has an edge to every other vertex.
\nWe call a complete graph with N vertices KN<\/sub>. For example, the figure over to the right is K6<\/sub>. When a complete graph is a subgraph of a larger graph, it’s called a *clique*. If removing the clique makes a connected graph become disconnected, then it’s called a *clique separator*. (Clique separators are very useful in graph coloring.)
\n\"k43.jpg\"
\nIf the vertices of a graph can be separated into two disjoint sets A and B such that every edge runs from a vertex A to a vertex in B, then we call it a *bipartite* graph. (Another way of stating this is that the graph can be 2-colored.) If there’s an edge from every node in A to every node in B, then we call it a *complete* *bipartite* graph. The complete bipartite graph between two sets A and B where A has N vertices, and B has M vertices, is
\ncalled KM,N<\/sub>. For example, over to the left is K4,3<\/sub>.
\nA bipartite graph
\ncan *never* include a cycle whose length is odd. There’s a remarkably simple proof. In a bipartite graph, every path must alternate A to B to A to B. Any cycle must necessarily follow the pattern of an edge from A to B, followed by a path, followed by an edge from B to A. The path must also follow a pattern: B to A, subpath, A to B. There’s no way to add to the potential cyclic paths in a bipartite graph without adding *two* edges.
\nIf a graph is connected and contains no cycles, then it’s called a *tree*. A disconnected
\ngraph whose connected components are all trees is called a *forest*. You can easily prove that every tree is bipartite. Take a node, and call it the root. Take the nodes connected it, and call them its children, and call the root its parent. For each of those nodes, call the nodes connected to them *their* children, and so on. Now, starting at the root, color the root one color, the children the other, the grandchildren the first, great-grandchildren the second, and so on.
\n\"petersen.jpg\"
\nA snark is, as I mentioned yesterday, a connected, bridgeless, cubic graph with chromatic index 4.
\nThe graph over to the right is called *Petersen’s graph*. Every snark contains
\nPetersen’s graph as a subgraph.
\n\"tree-factor.jpg\"
\nGiven a graph G, a subgraph is called a *spanning subgraph* if it includes every vertex
\nin G. If G is connected, a connected spanning subgraph that is a tree is called a *spanning tree*. Every connected graph has a *minimum spanning tree* – that is, a spanning tree such that no spanning tree can contain fewer edges. A spanning subgraph of G whose nodes all have degree N is called an *N-factor* of G. To the left, there’s a graph G; a spanning tree, and a one-factor.
\nGiven a graph G, if there is a cycle including every node, that’s called a *Hamiltonian cycle*. A graph can have multiple hamiltonian cycles.<\/p>\n","protected":false},"excerpt":{"rendered":"

Naming Some Special Graphs When we talk about graph theory – particularly when we get to some of the interesting theorems – we end up referencing certain common graphs or type of graphs by name. In my last post, I had to work in the definition of snark, and struggle around to avoid mentioning another […]<\/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-459","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7p","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/459","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=459"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/459\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=459"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=459"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=459"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}