# Talk:Graph (mathematics)

WikiProject Mathematics (Rated B+ class, Top-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 B+ Class
 Top Importance
Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
A selected article on the Mathematics Portal.
WikiProject Computer science (Rated B-class, High-importance)
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B  This article has been rated as B-Class on the project's quality scale.
High  This article has been rated as High-importance on the project's importance scale.

## Generalizations section

The previous text was this: Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs. Of course not all matroids correspond to graphs - that's the whole point of a generalization. The same applies to hypergraphs and any other generalization. I removed the remark.Wandrer2 09:28, 26 January 2007 (UTC)

## 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:22, 9 Jan 2005 (UTC) after that he did another theory —Preceding unsigned comment added by 217.38.127.254 (talk) 17:44, 4 September 2007 (UTC)

## Loops?

The current definition of "directed graph" allows loops. (And it did before I edited it!) I suggest that by default, a directed graph should not allow loops; that possibility should only be mentioned in the alternate definitions section. I'll make the change eventually unless there are objections. Dbenbenn 14:48, 13 Jan 2005 (UTC)

In my opinion it is easier to call a graph without loops simple graph and a graph with loops graph then the other way round. But you are free to change the definition. MathMartin 19:55, 18 Jan 2005 (UTC)
Well, I guess I mainly care about consistency between "graph" and "directed graph". It sounds like you think the definition of "graph" should be changed to allow loops. Anyone else have an opinion? dbenbenn | talk 02:47, 19 Jan 2005 (UTC)
Yes I would change the definition of graph to allow loops (my main concern is consistency too). I think it is easier having a broad definition for graphs and digraphs which includes loops and multiple edges than giving separate definitions. The broad definition can be narrowed down, if necessary, by using adjectives like simple. Another reason for the broader definition is to define a broader notion of graph homomorphism (as you have already noticed). But this is just my opinion. At the moment I am a bit busy so I am unable to work on either article. If you think you can make the definitions more consistent or clearer go ahead. MathMartin 13:47, 19 Jan 2005 (UTC)
The graph theory literature is divided on whether "digraph" allows loops. Whichever we give as the primary definition, the section on variations of definitions should mention the inconsistency. --Zero 09:21, 19 Jan 2005 (UTC)

Something the article should make more clear is which of the two intuitive concepts of loop it is referring to. It's one thing to have a line coming out from a node and back around directly in to the same node again. It's another to connect A-B-C-A.. Cesiumfrog (talk) 05:49, 1 October 2010 (UTC)

I'm not sure why there would be confusion. A loop is defined in the article to be an edge from a vertex to itself. The other notion is a cycle, and it's not really defined on this article (surprisingly enough).--Wgunther (talk) 15:18, 6 October 2010 (UTC)

## Oriented graphs

I question this: "A more fundamental difference is that, in a directed graph (or multigraph), the directions are fixed, but in an oriented graph (or multigraph), only the underlying graph is fixed, while the orientation may vary." I don't know what "may vary" means. It seems to me that an oriented graph consists of a pair (undirected graph, orientation). A given undirected graph can be oriented in different ways but these lead to different oriented graphs, not to the same oriented graph where the orientation has "varied". --Zero 00:25, 17 August 2005 (UTC)

## Variorum

JA: I will be making some comments on the variations in definitions and terminology, but just to keep my headings together I will locate everything on the Graph theory talk page. Jon Awbrey 19:10, 18 March 2006 (UTC)

## Articles for edge and node

The articles edge (graph theory), node (graph theory) and node (computer science) are essentially impossible to write since you cannot explain edge without explaining node and graph (graph theory) and vice-versa. Therefore, I made these articles redirect to graph (graph theory). ylloh 01:01, 15 April 2006 (UTC)

## Citation Style

JA: My recommendation is that we continue to use the citation styles that are standard in math journals, and avoid the use of footnotes. These things make the line spacing on the face article very jagged, make the text in the edit window very hard to proofread, they become almost impossible to maintain when there gets to be more than a few of them, they lead to information loss when the source data is too complex for the Ref format, and all in all they make the article look very amateurish and antiquated, as footnotes for citations were already being phased out in the late 60's, just from what I recall. Jon Awbrey 13:30, 27 June 2006 (UTC)

## unordered pair?

Could one explain what means the unordered pair used in the definition of the graph? It seems that there is no such an entry in wikipedia (and the Axiom of the unordered pair, is not what we want here, is it?). --Beaumont (@) 16:04, 18 October 2006 (UTC)

An "unordered pair" is just a set with two elements. Otherwise simply called a "pair". The adjective "unordered" is sometime added to emphasize that it is not an ordered pair. Perhaps a definition of the term "unordered pair" should be added to the "ordered pair" article, which unordered pair could then link to. Paul August 17:15, 18 October 2006 (UTC)
Ok I've now done the above. Paul August 17:25, 18 October 2006 (UTC)
Thanks. Actually, my post was motivated by the question "how do we define a loop in not directed graph". Formally, the set {v,v} collapses to the singleton {v} and it's no longer "a pair". Well, I do not think it's a big problem here, but perhaps someone knows a standard solution so that we could make it clear in the article --Beaumont (@) 22:57, 4 November 2006 (UTC)
You're welcome. You are correct that with the definition given in the article, a non-directed graph is not allowed to have loops. If you want to alow a non-directed graph to have loops, then you can simple drop the word "distinct" in the definition of edge given in the the article, taking the set {a, a} to be a "pair" with non-distinct elements (See Balakrishnan, V. K.; Schaum's Outline of Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0070054894.) Or more explicitly, you can define each edge to be either a one or two element subset of V, (See Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0849339820.) Paul August 23:55, 4 November 2006 (UTC)
Yeah, there isn't a single way of doing this that makes everyone happy. The most common approach is to hide the issue in sloppy terminology. Usually confusion is avoided. One place where the distinction matters is in enumeration, where loops are usually regarded as adding 2 to the degree of a vertex but nevertheless add only 1 to the row and column sums of the adjacency matrix. McKay 03:00, 5 November 2006 (UTC)

## Definition of a Graph

I think the 3rd bullet point of the definition of a graph should be moved into the paragraph below, it's not part of the definition of a graph, it just defines some extra terminology. --Llygadebrill 21:11, 26 February 2007 (UTC)

Done. YOu could have done it yorself. `'mikka 21:32, 26 February 2007 (UTC)

## Definition of a Vertex

I find strange that a formal definition might depend on sets of some kind of object that is never defined. What are vertices? I guess some description on what kind of object is required to be a vertex or node would add to the article. But as I understand, there is no requirement for vertices objects (they need not properties other than being comparable for equality, which is always the case for math objects). So the only modification I suppose necessary is to tell this in the text: "V is a set of mathematical objects of any kind; they are called vertices (or nodes)". Am I wrong? hmoraldo

You are right that the wording is sub-optimal but your suggested fix is not good. The story is, first, that V is a set (any set will do). And, second, that the elements of the set will henceforth be called "vertices". I'll try making a change. McKay 03:44, 12 March 2007 (UTC)
Thank you for your fast reply. Now I signed both messages with my brand new user account name. hmoraldo

## Quivers vs. representations of quivers

My understanding of quivers is that a quiver _is_ just a directed graph, and that a representation of a quiver attaches a vector space to each vertex and linear mappings to each edge. Could someone please correct me if I am wrong or otherwise comment?

Thanks SophomoricPedant 04:19, 3 June 2007 (UTC)

Since no one responded, I will adjust the wording to reflect the above distinction SophomoricPedant 04:19, 3 June 2007 (UTC)

## Implementation

Our team has created a very effective graph and network optimization tool: an open source library written in C++ language. We think that our project is matured enough to be mentioned here in external links section. Or we could create a brand new Wikipedia article for it that could be cited from here. Everybody who gets familiar with graphs wants to use them. If our library was mentioned here, the next step towards using graphs would be presented here. The name of our open source library is LEMON. Here you can get familiar with it.

Phegyi81 14:15, 14 June 2007 (UTC)

You dit it real nice.

?? ??

Since no one responded, I refer our library in External links section.

Phegyi81 11:14, 2 July 2007 (UTC)

## Linear Graph

Is seems like someone has written the definition of a linear graph based on the wrong definition of a graph. Can anyone verify this? If no one says otherwise, or beats me to it, I'll rewrite the definition later. BTW, would a linear graph be, by definition, connected? MagiMaster (talk) 22:13, 11 February 2008 (UTC)

## Graphs too complicated

I think graphs im Maths are too complicated and you never use them in every day life (jobs) —Preceding unsigned comment added by 88.108.216.138 (talk) 17:23, 27 February 2008 (UTC)

I'm a computer science student working in a computer networks division, and I'm using graphs in everyday life. So do traffic engineers, city engineers and a whole lot of people building the infrastructure you take for granted. -- 80.136.83.51 (talk) 12:27, 10 October 2008 (UTC)

## Include Euler and Hamiltonian graphs

Hamiltonian and Euler graphs are more important than others. Needs grouping graphs according to their applications- for a non-mathematician.

The articles Graph (mathematics) and Graph Theory overlap several things. Why did someone write like this? I recommend reworking both of them and combinig as a single article. In summary, we are trying to dump duplicate materials at different places. They are not well organized.

--Tangi-tamma (talk) 20:32, 6 April 2008 (UTC)

The Graph (mathematics) article covers the definition and basic properties of graphs, whereas the Graph theory article covers the area of mathematics called graph theory, its history, current problems and applications. I think they are separate topics, although there is bound to be some overlap between the articles. However, if you want to propose a merger, follow the instructions at Wikipedia:Merging_and_moving_pages#Proposing_a_merger. The cleanup tags are not appropriate for this situation, so I have removed them from both articles. Gandalf61 (talk) 08:16, 7 April 2008 (UTC)

## Definitions

As a mathematician working mostly in geometry and topology, I always find the "definitions" section in graph theory textbooks rather annoying since they often avoid defining the object at the proper level of generality. The same is true here which should make anyone who is reading this article carefully fairly confused. The main definition of a graph given in the article is already that of a simple graph. If edges are defined as two-element subsets of the vertex set, then you automatically exclude loop-edges and multiple edges. So what does it mean then to say that a "A simple graph is an undirected graph that has no self-loops and no more than one edge between any two different vertices"? Sounds like a tautology to me. In fact what is a self-loop in the sense of the main graph definition anyway?

The actual general definition of a graph (where both loop-edges and multiple edges are allowed; if I remember correctly, this is called a pseudo-graph) is something like this: a triple G=(V,E,j) where j is a function that assigns to every element e of E a subset of V consisting of one or two elements.

I understand that this is a Wikipedia article, not a mathematical textbook, but shouldn't the formal general definition of a pseudo-graph be contained somewhere in the article? Nsk92 (talk) 04:11, 21 May 2008 (UTC)

I agree. I have tried to generalise the initial definition so that it defines a pseudograph (which actually redirects to multigraph in Wikipedia). This is now consistent with the definition sequence in glossary of graph theory which gives a general definition of graph first, then defines simple graphs and multigraphs. I just hope I haven't achieved precision at the expense of clarity ! Gandalf61 (talk) 09:14, 21 May 2008 (UTC)
In terms of formalism, it is better now. However, you are still excluding loop-edges in the main definition, right? I understood the phrase "unordered pairs of vertices" to mean "unordered pairs of distinct vertices", although maybe this should be mentioned explicitly. In terms of clarity, the problem with the new version is that it refers to the notion of a multi-set, which is defined in another article and with which most people are probably not familiar. I looked up the multiset article and they do have a correct formal definition there. Still, there is something to be said for giving a self-contained presentation in this article. One possibility is to rewrite the main definition completely an define a graph as a triple consisting of two sets V and E and end-point assignment function. (My personal feeling is that the insistence on a graph being an ordered pair rather than an ordered triple is somewhat misguided, although it seems to be customary.) This might require a fairly substantial rewrite of the entire article which may not be that great of an idea. Another possibility is, after the main definition is stated, to give a more expanded commentary on what it actually means and how to think about a multi-set of pairs of vertices more formally. Nsk92 (talk) 12:09, 21 May 2008 (UTC)
I deliberately took the word "distinct" out of the definition, so that the two vertices that define an edge can be the same, which allows for loops (in my world, an 'unordered pair' is a multiset, so {X,X} is a perfectly good unordered pair). If we load too many subsidiary definitions into the article we will draw flak from folks who will say we have made it too complicated for the general reader. Your {V,E,A}-triple approach is interesting - the assignment function A would assign each edge in E to an unordered pair of vertices, right ? But it is heading still further into abstract territory, which some editors may have objections to. Anyway, I'll leave further improvements up to you. Gandalf61 (talk) 13:33, 21 May 2008 (UTC)
I added an explicit qualifier that the vertices in an unordered pair do not have to be distinct. I'll think some more about the organization of this article, but, to be honest, I am not sure if I want to work on it seriously. As I said, I am much more of a geometer/topologist myself and I personally actually tend to think about a graph as a 1-dimentional CW-complex. But I am certainly not going to advocate that approach here. Nsk92 (talk) 14:06, 21 May 2008 (UTC)

## Graph metrics

As a computer science student heavily working on computer networks, we are constantly talking about "Graph metrics" or "Network metrics". Is there a similar concept in the article? Should it be included? -- 80.136.117.67 (talk) 13:39, 5 October 2008 (UTC)

See Distance (graph theory) for graph metric. As for "network metrics", it may be both a metric for the network considered as a graph, as well as have other meanings. I will try to write something here, but "as a computer science student" why don't you do this yourselves as well? Twri (talk) 23:26, 10 October 2008 (UTC)

## Connected Graph

Is the concept of a connected graph too simple to be mentioned? Either the "Graph Types" or the "Properties of Graphs" section should mention "Connected Graph" or "a graph is called connected", if even a "finite graph" is explained. -- 80.136.83.51 (talk) 12:29, 10 October 2008 (UTC)

Done. Thanks for bringing it to an attention. Twri (talk) 23:16, 10 October 2008 (UTC)

## Subcategory suggestion

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

## Cube Graph

Under important graphs, should we add the n-cube? i.e. the graph of joining the vertices of a hypercube that differ by 1 bit when the vertices are in a bit stream?AndrewHarvey4 (talk) 06:55, 14 October 2008 (UTC)

## Multi- or simple?

It would be easy to start a war over ownership of the term graph, but I'll refrain—for now, anyway :-). Nsk92 asserted above that the definition was too narrow, and Gandalf61 agreed and changed it. Now, I see things differently. For me, and for lots of other practicing mathematicians, graph implies simple, and if you want your edges to be multisets, you're welcome to a different term for this different beast, namely multigraph. Edges of cardinality not equal to 2 are perfectly respectable entities and are emminently worth studying, they merely merit (to our way of thinking) different terminology.

Since tons of mathematicians would be in the same pew with me in this religious debate, I've adjusted the blurb acknowledging our usage. In particular, where it used to attribute the usage to "some authors," it now refers to "many authors."

Let the food fight begin!—PaulTanenbaum (talk) 21:28, 23 October 2008 (UTC)

In fact, on further reflection, I think I'll massage the entry to restore the simple, undirected, loopless notion as the first definition, label it as merely the most common, and then retain the current (more general) definition. I feel that this approach is likely the best compromise between my wish to avoid confusing the typical reader ("Whoa, that's not the way I've seen it!") and yours to avoid allowing too narrow a conception to set in. Any objections?—PaulTanenbaum (talk) 21:41, 23 October 2008 (UTC)
I don't particularly appreciate references to starting the "war over ownership", "religious debate" and "the food fight". If you are looking to start any of these, you should do that elsewhere, not on Wikipedia. On the substance of your edit, I don't actually have a problem with it. Regarding the article itself, it discusses graphs in general, including various models of them (simple graphs, multigraphs, directed graphs etc). That is perfectly appropriate and in that context it is useful to have a general definition which covers, as subcases, several different models. The substance of my previous comment was simply to make the definitions mathematically correct. If you want to have a separate article about simple graphs, I'd be fine with that even if it introduces a bit of duplication. I am not particularly interested in philosophical debates about terminology. I will say, however, that graphs with loop-edges and with multiple edges are very useful and natural objects in, for example, topology and group theory. (In fact, I think that many topologist define a graph, at least for themselves, as a one-dimensional cell complex). From the point of view of covering theory it is completely unnatural to exclude graphs with loop-edges and multiple edges from consideration. Same in group theory when Cayley graphs and graphs of groups are considered. I personally like Serre's model for the notion of a graph (a set of vertices, a set of edges, an involution on the set of edges corresponding to taking a formal inverse of an edge, plus an initial vertex function from the set of edges to the set of vertices) which also does not require the graph to be simple. But I am not here to start a "food fight", as you put it, and I think that people are perfectly entitled to their own little preferences and prejudices in this regard. Nsk92 (talk) 22:16, 23 October 2008 (UTC)
I think he was being facetious - he just wanted to start a calm discussion on the topic. The essential organization question here is whether we want this article to discuss simple graphs and to discuss multigraphs at multigraph, or whether we want this article to discuss multigraphs and simple graphs to be discussed at simple graph. I'd say the formal definition of multigraphs is simpler, which is nice for giving the initial formal definition, but for introductory examples, simple graphs are more appropriate. Loops and multiple edges can be introduced in separate examples. Dcoetzee 22:19, 23 October 2008 (UTC)
I think it makes perfect sense to have an article that discusses various models of graphs together, under one roof (and I think that the present article serves that purpose), and also to have a number of subarticles that are devoted to particular submodels. Nsk92 (talk) 22:28, 23 October 2008 (UTC)
(OK, guess I shoulda known my attempt at light-heartedness might come across wrong, so for that I apologize.) All I'm really proposing is to put the simple, loopless definition first, labeled as the most widely used,and then follow it with the other, labeled as the most general. Dcoetzee does raise a good point about the advisability of breaking out the bulk of the discussion on each flavor of object into separate articles that are pointed to by the master article, which summarizes the distinctions. Is that what I hear you to support as well?—PaulTanenbaum (talk) 22:46, 23 October 2008 (UTC)
I don't have particularly strong preferences about the order in which various notions are presented in the main body of the article. However, I do think that the lead section there should be a fairly general discussion, of general and not of very formal nature, about graph as a concept (nodes, arcs between them, with or without arrows, etc) that in some reasonable way covers most of the models of graphs that are later on discussed in the article. Nsk92 (talk) 00:46, 24 October 2008 (UTC)
My impression is that among the participants in this discussion, Nsk92 is the most serious expert in the field. It would make sense to defer to his opinion. Katzmik (talk) 10:07, 24 October 2008 (UTC)
Katzmik - one of the problems with the "defer to an expert's opinion" approach is that it is not how Wikipedia works - what we should do is reach consensus through discussion, and then implement that consensus. Having said that, PaulTanenbaum and Nsk92 seem to have almost reached a workable consensus anyway. Gandalf61 (talk) 10:20, 24 October 2008 (UTC)
Neither of us has the monopoly on setting wiki policy. What I wrote specifically is that I think "it would make sense" to defer to his opinion, based both on his expertise AND the quality of his contributions to date. Katzmik (talk) 10:23, 24 October 2008 (UTC)
Katzmik - I linked to Wikipedia:Consensus, which is a Wikipedia policy. You are, of course, free to express your disagreement with that policy, but that doesn't alter the fact that deferring to experts' opinions is not how Wikipedia works. It makes sense to me that editors should think for themselves. Gandalf61 (talk) 10:52, 24 October 2008 (UTC)
If I were you I would leave your motherhood and apple pie comments for your family. I resent the suggestion that I disagree with the consensus policy. I certainly agree with it. Excessive quoting of wikipedia policy I think is also looked down upon in wikipedia policy. Katzmik (talk) 10:59, 24 October 2008 (UTC)
Hmmm. It seems to me that your statements "Nsk92 is the most serious expert in the field. It would make sense to defer to his opinion" and "I certainly agree with <Wikipedia:Consensus>" are somewhat contradictory. However, as you have now descended to making derogatory personal comments (which contravenes another Wikipedia policy) I see no point in continuing this discussion. Gandalf61 (talk) 11:18, 24 October 2008 (UTC)
I've done as the consensus seemed to indicate. Enjoy.—PaulTanenbaum (talk) 14:34, 24 October 2008 (UTC)

## invariants

Would it make sense to have a minimal discussion of graph invariants, such as diameter, valence, girth, perhaps eigenvalue, etc? Katzmik (talk) 10:11, 24 October 2008 (UTC)

## To Bold or not to Bold?

I recently made this edit with an edit summary of: (See wp:manual of style#Italics "Italics are used sparingly to emphasize words in sentences (bolding is normally not used at all for this purpose).") About an hour later, User:Gandalf61 reverted my edit to this version with an edit summary of: (rv - bold text highlights defined terms, which is necessary in this overview article). Is this true? Is this the article where bolding can be used 74 times? (Yes, I did count them.) Any thoughts? 98.166.139.216 (talk) 19:50, 28 November 2008 (UTC)

I agree that most of these term definitions should be italics, per standard article style. Bold is only acceptable for terms which redirect here. Dcoetzee 08:44, 29 November 2008 (UTC)
I have no problem if the bold highlighting of defined terms is changed to italic highlighting. Note, however, that the original edit that I reverted had removed the highlighting of terms altogether. I oppose the complete removal of highlighting. Gandalf61 (talk) 10:19, 29 November 2008 (UTC)

## Applications?

I'd sure like to know why we have graphs. Just starting them in discrete math class, I find them fascinating, and I can't help but imagine they have countless real world applications, but there's no discussion of this on the page...could someone help? —Preceding unsigned comment added by 74.10.227.130 (talk) 20:49, 31 March 2009 (UTC)

You're right -- there are many real world applications. There is an applications section on the Graph theory page. It is most appropriate to have an applications section there and not here (in my opinion) Adammanifold (talk) 16:30, 21 May 2009 (UTC)

## File:Directed.svg Nominated for Deletion

 An image used in this article, File:Directed.svg, has been nominated for deletion at Wikimedia Commons in the following category: Deletion requests September 2011 What should I do? Don't panic; a discussion will now take place over on Commons about whether to remove the file. This gives you an opportunity to contest the deletion, although please review Commons guidelines before doing so. If the image is non-free then you may need to upload it to Wikipedia (Commons does not allow fair use) If the image isn't freely licensed and there is no fair use rationale then it cannot be uploaded or used. This notification is provided by a Bot --CommonsNotificationBot (talk) 19:45, 6 September 2011 (UTC)

## Equality vs Isomorphy

Missing: "Two graphs are said to be equal iff ...". Should follow each definition.

Also a word on isomorphy would be nice. — Preceding unsigned comment added by Modelpractice (talkcontribs) 22:47, 11 August 2012 (UTC)

## Graph Figure

Why is there figure of something that is *distinctly not a graph*, but a pseudograph, next to the definition? Would it not be much better to have a *graph* illustrating, you know, the definition of a *graph*?— Preceding unsigned comment added by 130.225.212.4 (talk)

## Why "edge"?

Please explain in the article why the word "edge" is used. If an "edge" is just a line, why isn't it called a line? If there is some subtle distinction that makes an "edge" not a line, it might be helpful to explain that. Alternately, if the meaning is identical but the term lives on for merely historical reasons, that would also be helpful to know. 129.219.155.89 (talk) 20:05, 2 April 2014 (UTC)

It is convention, but you'll note that the intro says: "Vertices are also called nodes or points, and edges are also called arcs or lines." I guess you don't have to draw edges "straight" for one distinction. Tom Ruen (talk) 20:30, 2 April 2014 (UTC)