Let’s talk a bit about graphs, being a tad more formal about them.
A 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 where a pair x={a,b} means that
vertices a and b are *adjacent*. We also say that edge x is *incident on* both a and b.
The number of edges that are incident on a vertex is called the *degree* of a vertex.
Take any graph G, and take the sum of the degrees of all vertices. That number will
be 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.
Already, 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.)
Ok, it’s trivial, but it’s cute. Moving on…
What 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 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).
On 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.
And now, just to get them out of the way, here’s a bunch of definitions:
* 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.)
* 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.
* 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.
* If there is at least one path from any node to any other node, then the graph is *connected*.
* If there’s a path from any node in the graph back to itself, then the graph is cyclic.
http://www.planarity.net is a game based on planer graphs.
Quick fix, Mark: In your first example of isomorphism, the two graphs *aren’t* isomorphic! Graph 1 has two vertices of degree 3 and two of degree 2, while Graph 2 has all vertices degree 2.
To get the suggested mapping to work, you’d need to add the edges (e,g) and (f,h) while removing (g,h).
Xanthir:
Are we seeing the same diagram? Both figures have 4 vertices with degree 3 – they’re both 4-cliques, just different arrangements of the vertices. (e,g) and (f,h) are edges in the graph.. Perhaps there’s an image scaling problem?
I also see the first image as *NOT* an isomorphism.
I don’t see an edge connecting a and b in the first graphic. In the second, the left graph doesn’t even look connected — there’s no visible edges from {a, b, e, f} to {c, d, g, h}.
The graphics looked like they’ve been scaled down. The scaler might’ve thrown out the lines of pixels representing some of the edges. I’ve seen that sort of thing happen with diagrams in a raster graphics file before.
Firefox 2.0.0.4 on Linux here, in case there’s some browser-specificness to the scaling.
I can confirm the issue is resolution, at least for me. The first isomorphism picture has been shrunk, the expanded version (doing a “view image” in Firefox will show this) has an edge from B->A, its just K_4 in both cases.
Well, I’ll add to the confirmation of an image scaling problem. In both Firefox and IE on Windows XP, the scaled image loses the edges (e,g) and (f,h). (Are Firefox and IE both calling the same subroutine to do the scaling, or is this just a coincidence?) In any event, this is a good illustration of why vector graphics should be used for this kind of application. I’ll be happy once SVG images (and MathML for that matter) are uniformly supported in browsers.
I see a graph with a and b not connected.
In the next pair of graphs I see a non-connected graph with no vertically drawn edges on the left.
If I look at the image itself (“view image” from the web browser) the vertical edges show up, so it’s probably a scaling problem.
“the number of edges in a graph is 1/3 the sum of the degrees of the vertices.”
Should that be 1/2 the sum of the degrees of the vertices?
If anybody is interested in the pre-history of graph theory and wants to know why the terminology is of “faces”, “edges” and “vertices” and/or is interested in the philosophy of mathematics and/or just likes reading brilliant science writing then they should read Imre Lakatos’ doctoral thesis Proofs and Refutations
A couple of problems:
– All figures except the clique has lost a few edges.
– The subset symbols only turns up in Western encoding, while IIRC this site used to support Unicode.
[Some of the scienceblogs sites seems to have started to force Western encoding at some posts, btw. It would be nice with a common and lax standard, preferably Unicode.]
– “u is adjacent to 2 vertices with degree 3 (v,z) and two with degree 4 (w,y)” should be:
u is adjacent to 2 vertices with degree 3 (v,y) and two with degree 4 (w,z).
So, eyeballing seems to indicate that cliques of order ≥ 5 aren’t planar? If it is correct, how do we prove that?
Eric:
I believe “a” graph refers not to any graph, but to a graph of the described kind (where the average degree of the vertices is three). That makes the argument go through.
Eric:
Yep, you’re right – silly typo. Fixed now.
I’ve tried increasing the size of the images – are the edges visible now? (On my mac, they were visible before rescaling, in both firefox and safari, so I’ve got no way to tell…)
Sorry about the image trouble; as I said, the images render fine on my machine. It’s frustating – I’m drawing the images in a vector graphics program, but I can’t post them in vector format…
In your second pair of graphs (the non-isomorphic ones) I’m still missing the vertical edges (a-c, b-d, e-g, f-h) in the first graph in FF 2.0.0.4.
I had to click on “view image” in Firefox to see all of the edges in the non-isomorphic picture (though the isomorphic one is fine).
Is this what topologists and geometers mean when they contrast global with local properties?
Ok, so I’m having a lot of fun with these posts. Thanks so much for posting them. I see how you can construct a planar 4-clique (since it’s pictured above.) Is there any way to construct a planar 5-clique? I don’t seem to be able to, but a proof by personal failure isn’t exactly convincing.
For really complicated graphs, Petri Nets as well as color can be helpful.
These use nodes for vertex, arcs for edges.
Also allowed are transitions sources/sinks and tokebs for quanta.
http://www.informatik.uni-hamburg.de/TGI/PetriNets/
Image
http://www.informatik.uni-hamburg.de/TGI/PetriNets/classification/level3/CPN.html
‘Metabolic Pathways’, for example, graphing may be better done with petri Nets?
http://www.manet.uiuc.edu/pathways.php
[Take any graph G, and take the sum of the degrees of all vertices. That number will be 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.]
This I do find trivial.
[Already, 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.]
I don’t find this trivial. One can’t draw a crisp graph with an odd number of vertices where the average degree of the vertices equals three. However, if we consider fuzzy digraphs, the sum of the degrees of all vertices can equal an odd number such as the graph
{{(a, b), 1/2}, {(a, c), 1/3}, {(b, c), 2/3}}, where
{(x, y), z} indicates that there exists a degree of connection z between x and y. Here vertex b has degree 2/3+1/2, and the sum of the vertices equals 3.
Mark:
I see, it was really the factual, not the hypothetical. That language works too, now that I see it in place.
Oh, and thanks for fixing the Unicode subsets!
The graphs are missing more edges in the new sizing, though. And I still don’t see how z is degree 3 and y degree 4 in your third figure. (Not that an eventual typo matters any longer – I am now fairly confident about the intended definitions.)
Ben:
That makes two of us. (See comment #11.) Still not exactly convincing, unfortunately. 😉
SpoonwoodDoug:
We’re talking about simple undirected graphs here – not fuzzy graphs. The statement that you’re complaining about isn’t true about digraphs, fuzzy graphs, or various other kinds of graphs.
planar 5-clique?
No!
“5-clique” = K_5 = complete graph on 5 vertices
Complete graphs are planar only for n less than or equal to 4. The complete bipartite graph K_(3,3) is nonplanar. More generally, Kuratowski proved in 1930 that a graph is planar iff it does not contain within it any graph that is a graph expansion of the complete graph K_5 or K_(3,3).
Weisstein, Eric W. “Kuratowski Reduction Theorem.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/KuratowskiReductionTheorem.html
Yep, I see all the edges now. The scaling just killed all the vertical edges.
Thanks, Mark!
Jonathan, thank you.
Btw, Mathworld was a good source on graphs – I see that planar graphs are the only ones with duals (the obvious geometric one, and interestingly an equivalent combinatorial dual), coming back to the eventual connection to spin physics mentioned in another post.
[We’re talking about simple undirected graphs here – not fuzzy graphs.]
I realized this.
[The statement that you’re complaining about isn’t true about digraphs, fuzzy graphs, or various other kinds of graphs.]
I didn’t have a ‘complaint’, at least not concerning your theorem. I said that I didn’t find your example ‘trivial’, basically because of the fuzzy case. In other words, I find your theorem more significant than you do, or at least more so than you did. I suppose you could reasonably maintain that I meant to ‘complain’ about your characterization of your proven statement as ‘trivial’.
I also consider it worth the time to actually detail the proof of your theorem as you did.
If G is a connected graph with infinitely many vertices such that every vertex has finite degree (that is, each vertex is adjacent to only finitely many other vertices) then every vertex of G is part of
an infinitely long simple path, that is, a path with no repeated vertices.
A common special case of this is that every tree that contains infinitely many vertices, each having finite degree, has at least one infinite simple path.
Note that the vertex degrees must be finite, but need not bounded: it is possible to have one vertex of degree 10, another of degree 100, a third of degree 1000, and so on.
For discussion and proof, and connection to logic and complexity and stuff, see:
http://en.wikipedia.org/wiki/Konig_lemma
Speaking of cliques and bipartite graphs, see the new:
arXiv:0706.4101
Title: Making a K_4-free graph bipartite
Authors: Benny Sudakov
Subjects: Combinatorics (math.CO)
We show that every K_4-free graph G with n vertices can be made bipartite by deleting at most (n^2)/9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete 3-partite graph with parts of size n/3.
This proves an old conjecture of P. Erdos.
Just a remark: in computer science, I’ve never seen a distinction being made between a graph and a *picture* of a graph. This is because for most applications of graphs it is completely irrelevant how graphs are displayed. It becomes relevant when designing support for graph supporting software, e.g. viewers or editors.
I like to call pictures of graphs *diagrams*. A diagram is a graph laid out on a 2D surface, i.e. positions (and possibly other properties such as size, shape, line width, etc.) are attached to its nodes, and a sequence of positions is attached to its edges (the “bend points”, usually 0 of them).
The distinction allows us to be a little more specific about the relationship between the pictures Mark has drawn and the notion of isomorphism: two graphs, say G1 and G2 are isomorphic if and only if some diagram of G1 is also a diagram of G2, and vice versa. (Which implies that *every* diagram of G1 is a possible diagram of G2, and vice versa.)
(The relationship becomes a little more complicated if we consider the fact that in diagrams nodes may obscure each other, or that we might want t display the same node multiple times. But that is just detail.)
So strictly speaking, it is not entirely correct to pretend that the first two diagrams above display different, but isomorphic graphs. But it’s the most convenient way to visualize isomorphism.
PS of course embedding graphs in the plane is very well studied in general, it just strikes me that it is often ignored when a graphical formalism is employed in computer science. It is more or less implicitly assumed that the graphs that will occur in practice will be easy enough to embed.
it is very nice