WikiProject Computing (Rated Start-Class)
	This article is within the scope of Computing WikiProject, an attempt to build a comprehensive and detailed guide to computers and computing. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
Start	This article has been rated as Start-Class on the quality scale
???	This article has not yet received a rating on the importance scale.

WikiProject Mathematics     (Rated Start-Class)
Mathematics portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	Top Priority	Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Detail on "Data structures" section doesn't really belong in article; "Problems in graph theory" needs more prose to accompany list items. Also needs more diagrams Tompw (talk) 13:41, 4 January 2007 (UTC) I disagree that Graph (data structure) should be disconnected from this article. I think it does belong among the list of subtopics. —David Eppstein 23:40, 21 April 2007 (UTC)

WikiProject Computer science      (Rated Start-Class)

Computer science portal v • d • e This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions. Start This article has been rated as Start-Class on the quality scale. Top This article has been rated as Top-importance on the importance scale.

Early Discussions

Info about directed graphs, including acyclic ones, would be nice to have too.

You can tell someone who's spent far too much time studying computer science when he refers to his ancestors as the "family directed acyclic graph".

I hope at least the last few nodes of your family DAG form a proper binary tree. Brent Gulanowski

2002

Maybe it's just me, but isn't it much more common to indicate graphs using the terms vertices and edges? Any formal defintion of graphs I've ever seen always uses these terms, G = (V, E). I know the other terms are also sometimes used, but I've never seen them in formal use, neither have I ever seen G = (N, E). Jeronimo

I agree. Vertices/edges is far more common than nodes/arcs. G=(V,E) is the standard notation. G=(N,E) is not only nonstandard, but it mixes the two nomenclatures. --LC 21:37 Sep 20, 2002 (UTC)

Maybe we need a few more pictures on this page; I moved the graphic down so that people wouldn't have to jump back and forth when considering the examples noted in the "properties" section; User:AxelBoldt moved it back so that people have a chance to see what the topic is about when they enter.

Perhaps smaller versions of the graphs shown at links like complete graph?

In addition, we could use a bit more meat here; graph isomorphisms, chromatic number, etc.; which might require a bit more overall restructuring. User:chas_zzz_brown 19:09 6 Oct 02 (UTC)

Ah, I just moved the graph down without realising there was some dispute over it. I will not move it back, though, because it seems clearly better where it is to me. It was more or less impossible to follow the examples with it stuck up at the top of the article without using a higher than normal resolution. If somebody wants to see it when they first get to the page, they can scroll down. --Camembert

I'm concerned about those people who are not mathematically mature enough and cannot follow the words without a picture. They won't scroll down, because they leave in frustration after the first paragraph. We can just show the same picture twice for now. AxelBoldt 19:35 Oct 6, 2002 (UTC)

Seems fair enough - if I'd realised there was some disagreement over where it should go, I would have done that myself. --Camembert

In addition, we could use a bit more meat here; Yup; maybe a section with elementary definitions like path, degree and cycle, and then a section with more substantive definitions like planar graph, coloring, Hamilton cycles etc and links to the respective pages. AxelBoldt 19:39 Oct 6, 2002 (UTC)

Arvindn, why did you remove the reference I put in to the Seven Bridges of Konigsberg problem? The page on Konigsberg and the page on Euler both mention this problem, which is a famous early problem in Graph Theory.

2003

Hi. I changed the definition of a null graph to say "a graph with no edges," but it was changed back to "a graph with no edges and no vertices." I don't think this is the most common definition of a null graph; in fact this is the first place I have seen it. I checked in MathWorld, and it appears that the definition used there, is the same as the one used here. But in all the books I have read a null graph may contain vertices. Fisk 16:41 Jan 24, 2003 (UTC)

I made the change after checking the first two Google hits, Mathworld and PlanetMath. The other links however seem to agree with your definition. The references given in the MathWorld article sound convincing however. I don't know what to do. AxelBoldt 02:30 Jan 28, 2003 (UTC)

How bout Networks topic?

Done. Mikkalai

2004

I typed "simple path" in the search box and it landed me here. I would fill in my own definition for a simple path if I could only figure out how to edit the simple path page. But I can't since it keeps landing me at Graph theory. Shouldn't there be a seperate page for things such as simple path? --Bryanlharris

Welcome, Bryan. Simple path. If you click there, you will see

Graph theory

(Redirected from [Simple path])

If you click on "simple path" there, you will see the page

Simple path

From Wikipedia, the free encyclopedia.

1. REDIRECT [graph theory]

And you can start editing.

BTW, if you type four tildas, ~~~~, it will give your signature with date. It helps us to tract conversations better.

Finally, in talk pages it is customary to add at the BOTTOM, not at the top of the page. I hope you will guess why.

Mikkalai 17:32, 6 May 2004 (UTC)

It seems that this page has been kinda stagnant for a little while. I just recently went through a grad class on the topic as well, and I'll probably fill in a few bits here and there as I have time to do so. I added a little bit on graph representations. I know that adjacency lists were covered by someone else in their own article, but I though that the adjacency matrix deserved a quick mention as well. I also added the special graph section, since there are several common graph structures which haven't been mentioned, from what I could see.

On second glance, it seems that this data may do better on the Graphs page. Don't have time to change it now, but I'll move it over soon. If anyone wants to do this for me, feel free.

--Naerbnic 07:14, 10 May 2004 (UTC)

2005

Merged graph (mathematics) into graph theory

I merged the two articles. See Wikipedia_talk:WikiProject_Mathematics#Graph_.28mathematics.29_vs_Graph_theory for a discussion. MathMartin 16:23, 9 Jan 2005 (UTC)

Rewording networks

I notice at the moment that networks (note no network at time of writing!) get a mention at the beginning of the article. However, I don't think the explanation is really right -- for a start, networks don't necessarily have weighted edges. I think it is probably better put as it is in network theory. There network theory (I prefer actually network analysis) is the applied mathematics of graph theory. How does a quick rewrite of the short network paragraph sound? -- as follows:

When graph theory is applied to real systems, it is called network analysis. A network can be used to model and analyze traffic networks, relations between people (social networks), or computer networks (like the internet).

--stochata 21:24, 30 Jan 2005 (UTC)

If I remember correctly the opening paragraph was rewritten by me some time ago. A network in mathematics is a graph with weighted edges (as far as I know) and the link is to network (mathematics) and not to network. This is a mathematics article so I think we should use the precise and common terminology (as used in mathematics). So I do not really understand what you mean be not really right, can you provide any links where a network (in mathematics) is defined without weighted edges ? Having said this the article definitely needs some more work and if you want to expand the introduction or add applications to the main article go ahead. MathMartin 22:05, 30 Jan 2005 (UTC)

You've actually helped me to work out what I meant by 'not right': as it is worded, the listed network topics (transport and the internet) are used in the sense of applied graph theory, whereas the sentence that introduces the network is the technical graph theoretic usage -- I'm from the applied end, so I'm not well acquainted with the terminology -- although it doesn't appear to be universally fixed within mathematics -- here's a quick googled link: [1] More importantly, though, within any applied area, even the more technical such as scale-free networks or small-world networks (unwritten on Wikipedia as yet, see Watts & Strogatz, Nature 393, 440 - 442 (04 Jun 1998) if you have access or small-world phenomenon), 'network' is used to mean simple a graph. Therefore it strikes me some clarification is necessary. As you say, this is a mathematics article, so yes, let's keep a technical definition of a weighted digraph, but also then suggest applied is looser with its definition? --stochata 01:58, 31 Jan 2005 (UTC)

Stochata is right! --Zero 08:42, 31 Jan 2005 (UTC)

I admit my focus is on mathematics and I do not work in applied graph theory. So if you think the sentence is unclear (and Zero does too), then be bold and go ahead and edit/clarify the article. By expanding the material the article can only become clearer. And I think it is a good idea to mention in the introduction that some people (for whatever strange reasons) refer to a simple graph as a network.MathMartin 11:20, 31 Jan 2005 (UTC)

Done, although it needs tidying up: now has a digraph twice --stochata 21:51, 1 Feb 2005 (UTC)

If you have a digraph with no loops( a group of vertices a[n] with a arrow going from a[j] to a[j+1] and a arrow going from a[n] to a[1]) it proveably has a vertice that no arrows point to is the problem of finding some or all of these vertices NP-Complete?--SurrealWarrior 02:49, 19 Jun 2005 (UTC)

2006

Hamilton's problem

Hamilton's problem (in History section) and Hamiltonian graphs need to be added.--Sahodaran 12:07, 20 January 2006 (UTC)

Graph/network of wikipedia

This might just be personal, but i've been interested in the network of wikipedia pages. It seems to me this would be both interesting and usefull, allowings sysops and users to classify articles more easily. Saganatsu 20:03, 1 March 2006 (UTC)

On the variety of definitions

• JA: It's best to put new comments at the bottom of the page.

Now, we have different definitions in "graph" and in "graph theory", does it make sense? kuszi 15:34, 15 March 2006 (UTC)

• JA: I'm in the process of going through the graph and graph theory articles, resolving the continuity problems as best I can. The fact that there are different defs in the field cannot be avoided, especially if you include computer science and category theory usages, but most of the bigger contentions were ironed out decades ago, and the main residual problem that we have is the different levels of sophistication in what are roughly equivalent definitions. So I am working on that. Jon Awbrey 15:48, 15 March 2006 (UTC)

Variorum

JA: I will be working on the Graph (mathematics) and Graph theory articles next week, especially to untangle some of the confusions over variant definitions and terminology, but I will be putting all or most of the associated remarks on this talk page. Jon Awbrey 19:16, 18 March 2006 (UTC)

Labels

I often see graphs referred to either as "labeled" or "labelled". My dictionary does not mention the former, so we should use the one with two L's, shouldn't we? Bender05 13:22, 23 March 2006 (UTC)

Labeled in USA, Labelled in UK. Use the one you prefer. Mariano(t/c) 13:31, 23 March 2006 (UTC)

Complexity of the definitions

Currently we have definitions like this:

An undirected graph or graph G is a 3-tuple G:=(V, E, δ_E) with

• V a set of vertices,
• E a set of edges or nodes,
• a function which maps each edge to its two vertices.

This is a perfectly good definition, but more complicated than necessary. Almost all (I mean > 99%) of papers in graph theory define E to be a set (or multiset) of pairs of elements of V and don't define δ_E at all. This is surely easier for a novice to understand, as well as being adequate for most professionals, so I propose we use it here. --Zero 23:17, 8 Jan 2005 (UTC)

I am not completely satisfied with my definition either, although I think the definition before was even worse. The reason for defining δ_E is to cleanly define graph homomorphism later on. If you have any ideas for simplifying the definition give it try, I will try tomorrow. MathMartin 00:13, 9 Jan 2005 (UTC)

I just noticed that the definition above is not correct. The addition "or nodes" (should be "or vertices") is presumably intended to include loops, but then δ_E should map the loop to a single vertex, not to a pair of distinct vertices which is all that (V choose 2) contains. Even if δ_E was extended to map into (V choose 2) union V, that would allow the bizarre possibility that a loop is mapped to a different vertex from the one it sits on. I think the root problem here is that we are attempting to be too formal. I would define an undirected graph like this:

An undirected graph or graph G is an ordered pair G=(V, E) where

• V is a set of vertices,
• E a set or multiset of edges, each of which is a set of 1 or 2 vertices.

Similarly "directed graph" has E a set or multiset of ordered pairs of vertices. A mixed graph has E containing both types.

A loop is just maped to the pair {v,v} where v is the vertice it sits on.--SurrealWarrior 02:53, 19 Jun 2005 (UTC)

A graph homomorphism from graph G=(V,E) to graph G'=(V',E') is a mapping from V to V' such that E is mapped to E'. (Since E is defined in terms of V rather than independently, the action on E is induced in an obvious way.) This works for undireced, directed and mixed graphs with the definitions I have suggested. The problems arise from trying to be too notational; English used carefully is just as precise. --Zero 01:27, 9 Jan 2005 (UTC)

Ok, I am finished. I moved the functions you did not like and the graph homomorphism section to graph homomorphism. I think this is a good solution. MathMartin 19:21, 9 Jan 2005 (UTC)

Now, we have different definitions in "graph" and in "graph theory", does it make sense? kuszi 15:34, 15 March 2006 (UTC)

I think there should be mathematical definitions instead of just text. Otherwise, the formal definition would be the same as the informal definition on top of the articles graph (graph theory) and graph theory. I wrote a not too complicated definition that was equivalent to the given textual definition in graph (graph theory) but it has been reverted. ylloh 12:50, 15 April 2006 (UTC)

JA: The Graph theory article is supposed to be the more complete article on graphs, with the Graph (mathematics) article being the more basic introduction. It's a natural human tendency for people to think that the definitions they learned at school are the only ones, or at least the most popular ones, but I think that this article currently covers most of the bases with fully mathematical definitions. The changes made a little while ago were confusing graphs with digraphs, so I reverted them. Please discuss any problems that you see, either with substance or with style of exposition, on the talk page first, as this article has had a long history and is fairly stable now. Thanks, Jon Awbrey 21:18, 15 April 2006 (UTC)

4-colour

I have added (unsolved) to the 4-colour theorem because the proof is not generally accepted —Preceding unsigned comment added by 84.194.170.235 (talk) 15:59, May 13, 2006

I've removed the "unsolved". I believe that the proof is generally accepted. Paul August ☎ 16:13, 13 May 2006 (UTC)

It is definitly accepted. Also accepted is the planar 5-colouring even if it was done with computer-assistance. Mariano(t/c) 10:49, 15 May 2006 (UTC)

Multiple types of classifications

I am reading The Handbook of Graph theory" now by CRC publishing in the first chapter they included literally hundreds of definitions. such as: Edge-Multiplicity, Simple adjacency, Dot graph etc. I am going to add a small section on those terms. Let me know if anyone has a better way to show them. The Isiah 00:48, 25 July 2006 (UTC)

Nodes, Points, Vertices

JA: All three of these terms are commonly used by graph theorists, sometimes even by the same person depending on context, so it's best to be flexible here, especially in informal examples and by way of relating to programming applications. Jon Awbrey 20:56, 8 August 2006 (UTC)

Overview section

There is no overview section for this article. The opening paragraphs are much too involved for a novice browsing Wikipedian, and will quickly turn him off and away from the article. I recommend shortening the introduction, creating a new section called OVERVIEW where most of our 'nerdy' terminology (currently in the intro paragraph) should be confined. A browsing Wikipedian desiring in depth information about precisely what Graph Theory is will continue on into it's depths on his own. Don't drown the browser in details before she is actually interested in the subject; interested users will browse right on through and appreciate the extra organization of the article. I tried this but was recommended to open a discussion so here it is! Thanks for considering my edit. // Brick Thrower 06:47, 28 August 2006 (UTC)

JA: Many math and sci articles in WP have decaff and regular versions, with links at the top to advise the reader which is which. This is the caffeinated cup. The companion article is the one on Graph (mathematics). Your changes had the effect of introducing incorrect terminology first, which is always hard to correct later for the novice, and which turns off the reader who does not need an overview. Jon Awbrey 07:32, 28 August 2006 (UTC)

BT: Okay, I see the other article now. Thanks. I browsed right to this through a direct link from the Category page. A redirect notice can help at the top of this article then. But now I am more confused. Are you saying that this is a master/detail relationship between these two articles? I thought each article stood on it's own merit, and linked to it's relevant references. The same diagram is used on each article. Shouldn't we migrate all that definition type stuff at the top of the article to graph (mathematics) if the articles have a caff/decaf relationship? My edits only linked in additional important terms in the sentences that were already there. I wanted to know what those items meant, I had to look them up, they are relevant, they were there before my edit. I yanked out the wordyisms "has for it's subject matter" and "informally speaking", introduced the Overview header, and the rest of the article was same text as before. The WikiPedia standard is to link in significant items the first time they become relevant. Set and object seem important enough to use in the first sentence, so they need to be linked. A browser shouldn't be forced to accept the primitives used in the article before they are defined. I believe the link to the non-specific object is correct, because objects in a set are definitely logical and don't have to be instantiated to a specific field, if that's what you meant by "incorrect terminology". // Brick Thrower 09:03, 28 August 2006 (UTC)

JA: I think there used to be a link to the intro article at the top of the page, but it looks like it got deleted. The folks in physics even have a pair of templates for this — I tried using that once, but apparently somebody thinks they own the patent rights to it. Go figure. The usual form in math articles is something like — well, I might as write it there as write it here. If somebody deletes it again, it's probably because they think it's redundant given the wiki link for graph in the first sentence. Who knows?

JA: On the other issues, I think that it's fair to say that math folk hereabouts have traditionally and quite sensibly looked to the standards of math writing that prevail in the Real World, and prefer to dedicate what spare time they have in writing articles on math, as opposed to haggling with the Wikipians — God love 'em, someone has to — who spend their days and nights cooking up new-fangled style sheets and redundant robotemplates, all in a never-ending quest for the ultimate regimentality of the human spirit. Jon Awbrey 12:52, 28 August 2006 (UTC)

BT: Okay, now I'm starting to like what I'm seeing in the article after some of your changes, but I still feel that set and object need to be linked in. All of the Wikipedia standards indicate that not only should the important words be linked, but they should be linked in the first time they are referenced. This article Graph Theory is not a tutorial to be set up only by 'math folk hereabouts'. With respect to linking in "important" words, please review the unique wiki presentation style guidelines:

• WikiPedia Guideline: Layout
• WikiPedia Guideline: Build the Web
• WikiPedia Guideline: General links
• WikiPedia Guideline: Context-relevant links
• WikiPedia Manual of Style: Internal Links

Deleted definition

The following section is deleted.

--Definition-

Main article: Graph (mathematics)

Definitions of graphs vary in style and substance, according to the level of abstraction that is approriate to a particular approach or application. For the sake of perspective, the following definitions present the same substance in two different styles:

First, a classic definition, that covers most of the essential ideas in a very short space:

A graph G consists of a finite nonempty set V = V(G) of p points together with a prescribed set X of q unordered pairs of distinct points of V. Each pair x = {u, v} of points in X is a line of G, and x is said to join u and v. We write x = uv and say that u and v are adjacent points (sometimes denoted u adj v); point u and line x are incident with each other, as are v and x. If two distinct lines x and y are incident with a common point, then they are adjacent lines. A graph with p points and q lines is called a (p, q) graph. The (1, 0) graph is trivial. (Harary, Graph Theory, p. 9).

Next, a style of definition that is preferred in some approaches and applications:

A graph or undirected graph G is an ordered triple G:=(V, E, f) subject to the following conditions:

• V is a set, whose elements are variously referred to as nodes, points, or vertices.
• E is a set, whose elements are known as edges or lines.
• f is a function that maps each element of E to an unordered pair of distinct vertices in V, referred to as the ends, endpoints, or end vertices of the edge.

V (and hence E) are usually taken to be finite sets, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case.

A digraph or a directed graph G is an ordered pair G:=(V, A) subject to the following conditions:

• V is a set, whose elements are variously referred to as nodes, points, or vertices.

• A is a set of ordered pairs of vertices, called arcs, arrows, or directed edges. An edge e = (x, y) is said to be directed from x to y, where x is the tail of e and y is the head of e.

Alternatively, a digraph or a directed graph may be defined as an ordered triple G:=(V, E, f) subject to the following conditions:

• V is a set, whose elements are variously referred to as nodes, points, or vertices.
• E is a set, whose elements are known as arcs, arrows, or directed edges.
• f is a function that maps each element in E to an ordered pair of vertices in V.

There are also some mixed type of graphs with undirected and directed edges.

See Glossary of graph theory for further definitions.

The definition is in the graph (mathematics) article. It is a very bad idea to duplucate artcles. It doubles the work of other editors trying to improve the text. It may also eventually lead to very different texts, which will be very confusion for readers.

I copied the text here just in case, to see if something is missing from graph (mathematics) and may be merged there. `'mikka (t) 15:45, 30 August 2006 (UTC)

Stop Wrecking This Article

JA: I'm sorry that some comp sci folks don't learn what graph theory is any better than they do, but that's no reason for them to mess over the subject for everybody else. Jon Awbrey 13:20, 6 September 2006 (UTC)

I deleted:

• a long and chaotic definition of a graph, the topic which belongs to graph (mathematics), where it can be properly maintained
• a naive explanation that basically amounts to explanation that ordinary (unweighted) graph has no any additional information, i.e., has no distances and no weights. Why don't you write that it does not have colors, thicknesses, widths, flavors, throughputs, embeddings, and all other things a graph does not have simply because it does not have them by definition? `'mikka (t) 15:44, 6 September 2006 (UTC)

JA: I tried to be polite, but you have turned this article to mush. Stop it. Jon Awbrey 15:52, 6 September 2006 (UTC)

JA: It is perfectly proper to repeat the informal definition in the lead of the comprehensive article. This is a perfectly proper expository technique. The rest of what you say is not on the topic of graph theory. There are already lots of comp sci articles on graphical datastructures. Comp sci folks are free to confuse as many folks as they can over there. Jon Awbrey 16:00, 6 September 2006 (UTC)

JA: I did not write that stuff about weights, and it does look like it could use a trim. Don't really care either way. Work on that if you like. Jon Awbrey 16:04, 6 September 2006 (UTC)

JA: You are not even reading the two articles carefully enough to recognize that it's not the same definitions in both places. The one given here is the slightly more advanced ordered triple version. Leave it where it is. Jon Awbrey 16:20, 6 September 2006 (UTC)

Different definitions are even worse. If yours is better, put it into the graph (mathematics) article. `'mikka (t) 04:48, 7 September 2006 (UTC)

Neutrality of this article is disputed

Its clear from the recent editing war that a flag needs to be placed on this article. I am also worried that there are campers here who don't want "their" work modified. This is a Wiki, people; If you don't want your work edited mercilously, don't submit it. Once you submit work it becomes the "public property" of Wikipedians. Jon Awbrey, this is not your personal article, get over it and WP:DICK. Allow this article to morph into something greater than it is now. "Math folks hereabouts" and "Comp sci folks" are both Wikipedians; please stop generalizing as it doesn't matter what your profession is, just as long as the article conforms to WikiStyle. // Brick Thrower 21:18, 6 September 2006 (UTC)

The issue is not about neutrality. Content forks are not allowed in wikipedia. You cannot have basically same things described in different articles in different way. It will eventually lead to further divergence and confusion for reader. The main definition of an object in quiestion (graph) must be only in the "graph" aricle. Period. There is nothing to dispute. It is an ironclad law of common sense in wikipedia. `'mikka (t) 04:52, 7 September 2006 (UTC)

BT: Don't misunderstand me. I agree with your position entirely. I attempted similar edits last month. I raise the Flag Of Dispute only to bring attention to administrators that there is another contrary opinion here that does not seem to accept yours, mine, and others edits, manually reverting good edits. Dual definitions is one of them. It seems clear to me that there is no participation in consensus on his part. This FOD is merely a marker that says, "We agree that there is a dispute here." In fact you are correct in asserting that there are established wiki standards which uphold the definition. I quoted some of them myself earlier on this page. I am hoping that intervention by a mediator will assist in setting things straight. // Brick Thrower 07:43, 7 September 2006 (UTC)

Better introduction

Can someone put in a better introduction? It'd probably be good to include a ONE SENTENCE explaination of what a graph is, such as "(a set of items, known as vertices, that are connected to each other by edges)" or somesuch. - JustinWick 07:41, 21 October 2006 (UTC)

Yes, I agree. Please be bold and try to make that edit yourself. There are some fundamentalists though who are adamant that such material does not belong here, so don't be surprised if your edits are revised back to the way it is now. This is just a friendly warning from someone who has tried to do just what you are saying. I will back you up on your efforts because I think a change is also needed, away from the Fundamentalists and towards Wikiism. Good luck. // Brick Thrower 12:09, 5 November 2006 (UTC)

Actually, one sentence does not mean a full definition. A good comparaison is Group theory, which does not at the beginning define what a group is, but rather what kind of applications group theory may have, as well as the different sub-topics exist in this theory. For sure, at least one or two sentences would be necessary at the beginning to give some intuition of what is going on and a simple definition of a graph and related concepts could be added in a section. Actually, the article would probably need some strong restructuration:

• data structure issue should be removed (one could maybe add a link to Graph (data structure) if needed in a See Also section),
• Instead of a list of problems, a comprehensive list of sub-topics (with maybe one or two fundamental problems) should be given with links:
  • algebraic graph theory
  • homomorphisms and coloring
  • enumerative graph theory
  • geometric graph theory
  • topological graph theory
  • extremal graph theory
  • random graphs theory
  • etc.
• A section on concepts should be added, including a short definition of a graph

What do you think? pom 17:40, 8 November 2006 (UTC)

I believe that graph theory is a complex, rich set of mathematical theories that are useful and beautiful, however most people think of graphs as pie charts or histograms, and I firmly believe that any article introduction should contain some kind of basic (if incomplete) definition that will prevent confusion and cut straight to the chase. I often read only the first paragraph of a Wikipedia article, and then some of the external links (usually the best part, IMHO, as domain specific webpages often outperform an encylopedia entry, no matter how well written and lovingly crafted). It'd be great for those who just wonder WTF Graph Theory is to be able to quickly find out without having to wade through all the complex mathematical details. I think your structuring would be really cool, I didn't take enough theory classes to really be competent in that without a lot of extra reading (not near a library at the moment) but let me know what I can do to help. And as for why I didn't just add in my edit, I wanted some good feedback (which I got), and why should I have to write a whole sentence all by myself? :) - JustinWick 09:18, 7 December 2006 (UTC)

Edit by XxjwuxX

XxjwuxX added the following line:

• It has been used worldwide to figure out the theory of graphs.

I changed it to the following:

• Research in this branch has enabled mathematicians across the globe to significantly advance the theory of graphs.

I think it probably needs a citation. I certainly didn't want to remove a useful contribution, however. Perhaps this is an attempt to experiment by adding something innocuous to a page? This is this user's first contribution, so I added a post to his talk page introducing him to Wikipedia. --Whiteknox 03:03, 21 November 2006 (UTC)

2007

Re: Geospatial Topology

This section has been merged into Graph Theory without any attempt to address the fundamental concepts which were the focus of the Geospatial Topology article. Primarily, my concern is the abscence of any discussion of this topic with regards to Geographic Information Systems, which Geospatial Topology was an attempt to address. As such, I request that this article make some mention of the GIS principles related within this image

or please reinstate the Geospatial Topology article, as it is related to the Geostatistics page, which is currently an important issue in Geography. SCmurky 02:45, 9 May 2007 (UTC)

What, if anything, do principles of GIS, geostatistics, and geography have to do with graph theory? —David Eppstein 03:07, 9 May 2007 (UTC)

I added a poster to offer some visual assistance. These topics are not explicitly graph theory, but contain certain features... In any case, whoever merged Geospatial Topology with Graph Theory, seemed to think these topics were next to identical. If you want to investigate, search for Geospatial Topology and you will see that you are redirected to Graph Theory... While containing features which are derived from graph theory and topology, Geospatial Topology is the manipulation of these principles for GIS functions. See poster. SCmurky 03:48, 10 May 2007 (UTC)

Ok, after looking at the old version of geospatial topology I see why it was merged: because the only content on that page was about graph theory, specifically the bridges of Königsburg, and there were no sources listed. It also doesn't help that Google scholar returns no hits for "geospatial topology", although it is possible to find some non-wiki uses of that phrase through a regular Google search. In order to make a successful separate article, I think you need (1) content that describes the subject in enough detail to make it clear that it is something other than just graph theory, and (2) sufficient scholarly sources using that phrase in a consistent way to back up the assertion that it is a well-defined topic deserving of a separate article. —David Eppstein 03:57, 10 May 2007 (UTC)

I will find some references, given some time. I need to remove the link to Graph Theory though. ~ —The preceding unsigned comment was added by Bohunk (talk • contribs) 01:52, 15 May 2007 (UTC).

Drawing graphs section

I think Drawing graphs section should be moved from this article to Graph (mathematics). Any objections? Andreas Kaufmann 11:15, 21 October 2007 (UTC)

Only if the data structures section moves with it — I think they belong together (one being representation within a computer, the other being representation in a visual medium). But in general I'm not seeing a clear distinction or rationale for what's been included in this article vs what's included in that one, and I'd like to see such a rationale articulated — if we could agree on that, it would be easier to decide where to place particular subtopics, I think. —David Eppstein 15:31, 21 October 2007 (UTC)

It doesn't hurt to have a small section with a main link, perhaps even in both articles. Or merge the Graph (mathematics) and Graph theory rather than moving things between them. Dicklyon 16:38, 21 October 2007 (UTC)

Actually, I believe "data structures section" belongs to "graph" article as well. I would expect from this article a broader overview of graph theory. The following is missing currently in this article:

• Overview of different sub-fields (see "See also"/"Subareas").
• Are there any important theorems which should be explained?
• Better overview of graph algorithms. Andreas Kaufmann 17:05, 21 October 2007 (UTC)

2008

Terminology

The article is strongly biased to computer-science. OK, but can somebody at least write a section on terminology? I was going to give somebody a link to this article, but it does not even define adjacent vertices! Commentor (talk) 05:02, 19 March 2008 (UTC)

You want Glossary of graph theory, which is already linked from this article. Dcoetzee 04:17, 22 April 2008 (UTC)

And we should also avoid using graph terms before defining them in the article; I added a def'n for adjacent. Dicklyon (talk) 04:30, 22 April 2008 (UTC)

Ferrers diagram

I have removed the following text from the article:

Ferrars diagram to represent graphs

For a graphical partition p = (f₁, f₂, ₃,...f_l), the associated Ferrars graph is an array of l rows of dots, where row i has p_i dots and rows are left justified.

The graphs are represented by Ferrars diagram similar to adjacency matrix.

Removed because a Ferrers diagram is not a graph and does not represent a graph and so does not belong in an article on graph theory. A best it might be used to represent the frequency partition of a graph - but many graphs can have the same frequency partition. Gandalf61 (talk) 13:14, 21 April 2008 (UTC)

I'm not saying that Ferrers diagram is graph. It is a structure similar to the adjacency matrix of a graph. These structures are used to store.

Yes, somebooks and papers refer Ferrers as Ferrars. Earlier versions of mathworld used both of these. Consult Consensus before you decide to delete one more time. (I do not have any thing to say). Hopefully Eppesin D. will help us to draw the diagram for this new structure. Thanks.

--Tangi-tamma (talk) 23:42, 21 April 2008 (UTC)

I'm afraid Gandalf is quite right. A Ferrers Diagram is not a graph in the graph theory sense; it's more like the graph of a function, just a visual depiction of a structure. Dcoetzee 04:16, 22 April 2008 (UTC)

Algorithmic graph theory

Is there enough algorithmic material to move into a separate article? At present this is just a general redirect. Richard Pinch (talk) 11:22, 19 June 2008 (UTC)

I believe so. I suggest Graph algorithm for a title. Dcoetzee 17:25, 31 July 2008 (UTC)

Archiving talk page

Is anyone opposed to me archiving the talk page posts from >6 months ago? I can keep some out selectively if they would serve to stop people from repeating past problems, but I find that doesn't work terribly well. Protonk (talk) 16:39, 31 July 2008 (UTC)

Subcategory suggestion

Please see Category talk:Graphs#Subcategory suggestion. Twri (talk) 17:21, 10 October 2008 (UTC)