View source for Talk:Graph (discrete mathematics)

{{WikiProject banner shell|class=C|vital=yes|1=
{{WikiProject Mathematics|importance=top|portal=Y}}
{{WikiProject Computer science|importance=high}}
}}
{{annual readership}}

== 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.[[User:Wandrer2|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. [[User:MathMartin|MathMartin]] 16:22, 9 Jan 2005 (UTC)
after that he did another theory  <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/217.38.127.254|217.38.127.254]] ([[User talk:217.38.127.254|talk]]) 17:44, 4 September 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== 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.  [[User:Dbenbenn|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. [[User:MathMartin|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?  [[User:Dbenbenn|dbenbenn]] | [[User talk: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. [[User:MathMartin|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.  --[[User:Zero0000|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.. [[User:Cesiumfrog|Cesiumfrog]] ([[User talk: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).--[[User:Wgunther|Wgunther]] ([[User talk:Wgunther|talk]]) 15:18, 6 October 2010 (UTC)

I am surprised why a directed graph should _not_ allow self loops. While literature may offer mutually exclusive definitions, at least the articles on Wikipedia should not contradict one another. Compare https://en.wikipedia.org/wiki/Loop_(graph_theory)#Degree: "For a directed graph, a loop adds one to the in degree and one to the out degree." – This directly contradicts the definition on this page (x/=y). [[Special:Contributions/2601:647:5C00:4460:0:0:0:AA8E|2601:647:5C00:4460:0:0:0:AA8E]] ([[User talk:2601:647:5C00:4460:0:0:0:AA8E|talk]]) 17:31, 4 October 2021 (UTC)

The current definition of degree says that a loop is counted twice. A bit later in the page it says the maximum degree for a graph of n vertices (with loops) is n. I believe this should be n+1.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2601:1C2:1B7F:9FA0:441D:A012:C730:FECF|2601:1C2:1B7F:9FA0:441D:A012:C730:FECF]] ([[User talk:2601:1C2:1B7F:9FA0:441D:A012:C730:FECF#top|talk]]) 03:44, 29 November 2022 (UTC)</small> <!--Autosigned by SineBot-->

:I decided to just edit the page. I'm pretty confident the existing text was wrong. [[Special:Contributions/2601:1C2:1B7F:9FA0:441D:A012:C730:FECF|2601:1C2:1B7F:9FA0:441D:A012:C730:FECF]] ([[User talk:2601:1C2:1B7F:9FA0:441D:A012:C730:FECF|talk]]) 03:59, 29 November 2022 (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". --[[User:Zero0000|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.  [[User:Jon Awbrey|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)]]. [[User:Ylloh|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.  [[User:Jon Awbrey|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?). --[[User:Beaumont|<small>Beaumont</small>]] [[User_Talk:Beaumont|<small><span style="color:#118811">(@)</span></small>]] 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. [[User:Paul August|Paul August]] [[User_talk:Paul August|&#9742;]] 17:15, 18 October 2006 (UTC)
::Ok I've now done the above. [[User:Paul August|Paul August]] [[User_talk:Paul August|&#9742;]] 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 --[[User:Beaumont|Beaumont]] [[User_Talk:Beaumont|<small><span style="color:#118811">(@)</span></small>]] 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}}.) [[User:Paul August|Paul August]] [[User_talk:Paul August|&#9742;]] 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. [[User:McKay|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. --[[User:Llygadebrill|Llygadebrill]] 21:11, 26 February 2007 (UTC)
:Done. YOu could have done it yorself. `'[[user:mikkalai|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? [[User:Hmoraldo|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. [[User:McKay|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. [[User:Hmoraldo|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
[[User:SophomoricPedant|SophomoricPedant]] 04:19, 3 June 2007 (UTC)

Since no one responded, I will adjust the wording to reflect the above distinction
[[User:SophomoricPedant|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. [https://lemon.cs.elte.hu/site/ Here] you can get familiar with it.

[[User:Phegyi81|Phegyi81]] 14:15, 14 June 2007 (UTC)

You dit it real nice.

[[User:??|??]] ??

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

[[User:Phegyi81|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? [[User:MagiMaster|MagiMaster]] ([[User talk: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)  <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/88.108.216.138|88.108.216.138]] ([[User talk:88.108.216.138|talk]]) 17:23, 27 February 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
: 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. -- [[Special:Contributions/80.136.83.51|80.136.83.51]] ([[User talk: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. 

--[[User:Tangi-tamma|Tangi-tamma]] ([[User talk: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. [[User:Gandalf61|Gandalf61]] ([[User talk: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? [[User:Nsk92|Nsk92]] ([[User talk: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 ! [[User:Gandalf61|Gandalf61]] ([[User talk: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. [[User:Nsk92|Nsk92]] ([[User talk: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. [[User:Gandalf61|Gandalf61]] ([[User talk: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. [[User:Nsk92|Nsk92]] ([[User talk: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? -- [[Special:Contributions/80.136.117.67|80.136.117.67]] ([[User talk:80.136.117.67|talk]]) 13:39, 5 October 2008 (UTC)
:See [[Distance (graph theory)]] for [[graph metric|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? [[User:Twri|Twri]] ([[User talk: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. -- [[Special:Contributions/80.136.83.51|80.136.83.51]] ([[User talk:80.136.83.51|talk]]) 12:29, 10 October 2008 (UTC)
:Done. Thanks for bringing it to an attention. [[User:Twri|Twri]] ([[User talk:Twri|talk]]) 23:16, 10 October 2008 (UTC)

Fellows, when defining connected graphs, woudn`t be useful to define what is a "path" (in opposition to "edge")? I mean, a path of length 1 is merely an edge - and that worth mentioning to clarify someone who is unfamiliar with this theme [[User:hferro|hferro]]  <!--Template:Undated--><small class="autosigned">—Preceding [[Wikipedia:Signatures|undated]] comment added 01:26, 4 October 2016 (UTC)</small> <!--Autosigned by SineBot-->

== Subcategory suggestion ==

Please see [[Category talk:Graphs#Subcategory suggestion]]. [[User:Twri|Twri]] ([[User talk: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?[[User:AndrewHarvey4|AndrewHarvey4]] ([[User talk: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 :-).  [[User:nsk92|Nsk92]] asserted above that the definition was too narrow, and [[User:Gandalf61|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!—[[User:PaulTanenbaum|PaulTanenbaum]] ([[User talk: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?—[[User:PaulTanenbaum|PaulTanenbaum]] ([[User talk: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 [[Jean-Pierre Serre|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. [[User:Nsk92|Nsk92]] ([[User talk: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. [[User:Dcoetzee|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. [[User:Nsk92|Nsk92]] ([[User talk: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.  [[User:Dcoetzee|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?—[[User:PaulTanenbaum|PaulTanenbaum]] ([[User talk: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. [[User:Nsk92|Nsk92]] ([[User talk: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.  [[User:Katzmik|Katzmik]] ([[User talk: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 [[WP:CONSENSUS|consensus]] through discussion, and then implement that consensus. Having said that, [[User:PaulTanenbaum|PaulTanenbaum]] and [[User:Nsk92|Nsk92]] seem to have almost reached a workable consensus anyway. [[User:Gandalf61|Gandalf61]] ([[User talk: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. [[User:Katzmik|Katzmik]] ([[User talk: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. [[User:Gandalf61|Gandalf61]] ([[User talk: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. [[User:Katzmik|Katzmik]] ([[User talk: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 [[WP:NPA|another Wikipedia policy]]) I see no point in continuing this discussion. [[User:Gandalf61|Gandalf61]] ([[User talk:Gandalf61|talk]]) 11:18, 24 October 2008 (UTC)
::::::Woa, take it easy. My opinion certainly should not count more than anybody else's opinion here. People should listen to what others say and then make up their own minds and express their opinions. I am also not any kind of an expert in graph theory: I am a [[geometric group theory|geometric group theorist]] and my perspective is colored accordingly. There are real graph theory experts here, including [[User:PaulTanenbaum|PaulTanenbaum]] and [[User:David Eppstein|David Eppstein]]. But this article is of rather general nature, where the main issues are those of style, presentation and organization, not of some deeply technical knowledge. As I said, if the article starts with a lead section discussing the concept of a graph informally and in some generality covering most basic graph models used in mathematics, followed by a more detailed list list of such models with more formal definitions, I'll be quite satisfied. There may be good reasons (such as tradition and perhaps simplicity of definition) to start with simple graphs and make something of an emphasis on them, I don't have strong feelings here. In fact, I have to say that I don't have a particularly strong interest in this article. I only commented here back in May because at the time the presentation was mathematically inconsistent. [[User:Nsk92|Nsk92]] ([[User talk:Nsk92|talk]]) 13:47, 24 October 2008 (UTC)

:I've done as the consensus seemed to indicate.  Enjoy.—[[User:PaulTanenbaum|PaulTanenbaum]] ([[User talk: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?  [[User:Katzmik|Katzmik]] ([[User talk:Katzmik|talk]]) 10:11, 24 October 2008 (UTC)

== To Bold or not to Bold? ==

I recently made this {{diff|Graph (mathematics)|254617770|251383387| 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 {{diff|Graph (mathematics)|254623504|254617770|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?  [[Special:Contributions/98.166.139.216|98.166.139.216]] ([[User talk: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. [[User:Dcoetzee|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. [[User:Gandalf61|Gandalf61]] ([[User talk: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?  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/74.10.227.130|74.10.227.130]] ([[User talk:74.10.227.130|talk]]) 20:49, 31 March 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

: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) [[User:Adammanifold|Adammanifold]] ([[User talk:Adammanifold|talk]]) 16:30, 21 May 2009 (UTC)
==File:Directed.svg Nominated for Deletion==
{|
|-
| [[File:Image-x-generic.svg|100px]] 
| An image used in this article, [[commons:File:Directed.svg|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 [[WP:NFCC|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 [[WP:FUR|fair use rationale]] then it cannot be uploaded or used.

''This notification is provided by a Bot'' --[[User:CommonsNotificationBot|CommonsNotificationBot]] ([[User talk: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.  <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Modelpractice|Modelpractice]] ([[User talk:Modelpractice|talk]] • [[Special:Contributions/Modelpractice|contribs]]) 22:47, 11 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->



==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*?<span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/130.225.212.4|130.225.212.4]] ([[User talk:130.225.212.4|talk]]) </span><!-- Template:Unsigned IP -->

== 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. [[Special:Contributions/129.219.155.89|129.219.155.89]] ([[User talk: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. [[User:Tomruen|Tom Ruen]] ([[User talk:Tomruen|talk]]) 20:30, 2 April 2014 (UTC)

== Requested move 5 January 2016 ==

<div class="boilerplate" style="background-color: #efe; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px dotted #aaa;"><!-- Template:RM top -->
:''The following is a closed discussion of a [[WP:requested moves|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a [[Wikipedia:move review|move review]]. No further edits should be made to this section. ''

The result of the move request was: '''no consensus''' unfortunately. While there is general agreement that the current title is problematic, there is clearly no consensus as to how exactly this article should be renamed. Seeing as the discussion here has died, I'm closing this discussion because I think the chances of it reaching a consensus for any of the proposed variants to be almost nonexistent. No prejudice against any new RMs if anyone can think up a title they think will gain a consensus. [[User:Jenks24|Jenks24]] ([[User talk:Jenks24|talk]]) 09:46, 25 January 2016 (UTC)

----


[[:Graph (mathematics)]] → {{no redirect|Graph (discrete mathematics)}} – Users often incorrectly point to [[Graph (mathematics)]] when they actually mean [[Graph of a function]]. [[Graph (mathematics)]] should be redirected to [[Graph (disambiguation)#Mathematics]]. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 11:48, 5 January 2016 (UTC)<small>--'''Relisted.''' [[User:Cuchullain|Cúchullain]] [[User talk:Cuchullain|<sup>t</sup>]]/[[Special:Contributions/Cuchullain|<small>c</small>]] 14:54, 13 January 2016 (UTC)</small>
* '''Oppose''' – the extra disambiguation is not warranted.  How some editors mislink is not really a title criterion.  [[User:Dicklyon|Dicklyon]] ([[User talk:Dicklyon|talk]]) 05:48, 6 January 2016 (UTC)
*: Per [[WP:PRECISION]], "Usually, titles should be precise enough to unambiguously define the topical scope of the article, but no more precise than that." Because [[Graph (mathematics)]] is ambiguous and none of its meanings is [[WP:primary topic]], it should be disambiguated. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 13:24, 6 January 2016 (UTC)
*'''Support''' move. You are right that the current disambiguation is insufficient, but I think [[Graph (graph theory)]] would be better, since that topic is discussed more than discrete mathematics, and the page is in [[:Category:graph theory]] rather than [[:Category:discrete mathematics]]. '''[[User:kennethaw88|kennethaw88]]''' • [[User talk:kennethaw88|talk]] 05:50, 6 January 2016 (UTC)
*: [[Graph (graph theory)]] is acceptable for me. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 13:24, 6 January 2016 (UTC)
*: [[Graph (mathematics)]] belongs to [[:Category:graph theory]], which belongs to [[:Category:combinatorics]], which belongs to [[:Category:discrete mathematics]].  --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 15:46, 13 January 2016 (UTC)

* '''Support''' move to {{noredirect|Graph (graph theory)}}: in fact,  {{no redirect|Graph (discrete mathematics)}} is almost as ambiguous as [[:Graph (mathematics)]], because the [[graph of a function]] defined over a discrete domain makes sense and is widely used in discrete mathematics. Moreover, while "Graph theory" is clear for everybody, "discrete mathematics" is not. For example I see that [[coding theory]] and [[cryptography]] are not listed in [[Discrete mathematics topics]]. Myself, I am unable to say which parts of my research domain ([[computer algebra]] and [[Computational algebraic geometry]]) belong to discrete mathematics. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:45, 6 January 2016 (UTC)
:: Largely your examples highlight that the article [[discrete mathematics topics]] is not a very good article.  By contrast, Category:coding theory is contained in Category:discrete mathematics, as it should be. --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]])
* I strongly support [[Graph (discrete mathematics)]], weakly oppose [[Graph (graph theory)]] -- the latter usage is only clear to people who already know what the object in question is, who won't be making this mistake; there is no possibility of confusion about [[graph (discrete mathematics)]], and graphs are studied in a larger area of mathematics than just graph theory. --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 16:29, 6 January 2016 (UTC)
*'''Comment'''. It sounds like we have consensus to move away from [[Graph (mathematics)]], but I'm relisting so we can get consensus between the two options [[Graph (discrete mathematics)]] or [[Graph (graph theory)]].--[[User:Cuchullain|Cúchullain]] [[User talk:Cuchullain|<sup>t</sup>]]/[[Special:Contributions/Cuchullain|<small>c</small>]] 14:54, 13 January 2016 (UTC)
*'''Comment'''.  A move is probably a good idea if we can agree on a title.  [[Graph (graph theory)]] is problematic for the reasons stated by JBL.  [[Graph (discrete mathematics)]] is problematic for the reasons stated by D.Lazard.  Shall we try [[Graph (combinatorics)]]?  <small><span style="display:inline-block;vertical-align:-.3em;line-height:.8em;text-align:right;text-shadow:black 1pt 1pt 1pt">[[User:Slawekb|<big>S</big>ławomir]]<br/>[[User talk:Slawekb|<span style="color:red;">Biały</span>]]</span></small> 16:05, 13 January 2016 (UTC)
*'''Comment'''. Maybe "Graph (mathematical structure)" versus "Graph (of a function)"? [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 16:28, 13 January 2016 (UTC)
*'''Support''' move to [[Graph (discrete mathematics)]]. I think the phrase "discrete mathematics" is less ambiguous than "graph theory", if you don't already know what graph theory is. Also, the English word "discrete" is helpful, even without knowledge of the mathematics. [[User:Mark L MacDonald|Mark MacD]] ([[User talk:Mark L MacDonald|talk]]) 16:55, 13 January 2016 (UTC)
*'''Support''' a move and this made a disambiguation. And in fact 'Graph of a function' is probably the wrong name for that and it should be widened slightly as for instance in a relation the graph is not necessarily a functional one. Can't think what better name to use though. [[User:Dmcq|Dmcq]] ([[User talk:Dmcq|talk]]) 17:19, 13 January 2016 (UTC)
*'''Weakly in favor of [[Graph (discrete mathematics)]]''', because I think that graphs are heavily used throughout this large area of mathematics, not only in graph theory. This title also makes it clear that the concept belongs to mathematics, and only to some specific part of it. So the user is forced to check whether the concept, that he is thinking about, matches the article. Discrete functions, like sequences, belong rather to [[mathematical analysis]] than to discrete mathematics, so I think the probability of confusion is low. '''[[Graph (graph theory)]]''' is a sort of circular reference and it does not make clear that it belongs to mathematics. '''[[Graph (combinatorics)]]''' appears a bit too narrow to me. '''[[Graph (mathematical structure)]]''' is almost equivalent to [[Graph (mathematics)]]. I also considered '''[[Graph (network)]]''', but maybe that could be confused with computer engineering. Or how about '''[[Graph (connected nodes)]]'''? Anyway, in the end, the actual title almost does not matter. The most important thing is that the user is reminded that mathematics has more than one concept called graph. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 19:20, 13 January 2016 (UTC)
*'''Comment'''. A hard case! Maybe "Graph (a network of lines connecting points)" versus "Graph (a set that represents a function or relation)"? [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 19:14, 13 January 2016 (UTC)
*: Tee-hee.  Your earlier suggestion "Graph (mathematical structure)" seems reasonable to me, although I still prefer "Graph (discrete mathematics)".  --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 19:18, 13 January 2016 (UTC)
::: How about [[Graph (insert this entire present discussion here, but first wait until it exceeds one-hundred-thousand words)]]? [[User:Michael Hardy|Michael Hardy]] ([[User talk:Michael Hardy|talk]]) 22:17, 13 January 2016 (UTC)
:::: If we do the insertion recursively, we don't have to wait ;).  --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 22:30, 13 January 2016 (UTC)
*'''Comment'''. Then, indeed, "Graph (connected nodes)" versus "Graph (of function or relation)". [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 20:00, 13 January 2016 (UTC)
*'''Oppose''' any decisioin on this until we discuss this more and come up with a better choice of names. The "discrete mathematics" and "combinatorics" disambiguators are inaccurate as some graphs are far from discrete or combinatorial (see the [[Hadwiger–Nelson problem]], [[Hyperbolic group]], and [[Rado graph]] for graphs that have much more to do with Euclidean geometry, group theory, and model theory than they do with combinatorics). And if "Graph (graph theory)" is good, why isn't "Graph (graph (graph theory) theory)" better?  They both explain equally well what a graph is. Boris's suggestions involving connectivity are even worse because not all graphs are connected. I agree there is a problem (the ambiguity between node-link graphs and function domain-range graphs) but I don't think these solutions have been adequately thought through. We should have a proper discussion before any vote on whether we like the new name, not voting first (with random interspersed alternative names confusing the vote). My own preference would be to replace this article with a proper article on [[undirected graph]] just as we have one for [[directed graph]] and [[mixed graph]], and move the discussion of types of graph into [[graph theory]]. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 01:28, 14 January 2016 (UTC)
*'''Comment'''. I essentially agree with David's comments above and think that [[undirected graph]] might be the way to go. [[Graph (mathematics)]] is clearly a poor choice and I prefer [[Graph (combinatorics)]] to [[Graph (discrete mathematics)]] since I don't think that discrete mathematics is a well defined area and I've always felt that the essential part of graph theory has been a subtopic of combinatorics. I would want to avoid getting too fancy with the disambiguators and let the disambiguation page [[Graph]] do what it is meant to do.[[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 04:57, 14 January 2016 (UTC)
----
:''The above discussion is preserved as an archive of a [[Wikipedia:Requested moves|requested move]].  <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page or in a [[Wikipedia:Move review|move review]]. No further edits should be made to this section.''</div><!-- Template:RM bottom -->

== We are Buridan's ass ==

Indeed, we have several possible moves, each being better than nothing; however, we do nothing, since we do not know which possibility is optimal; just [[Buridan's ass]]. Could we choose one possibility randomly? [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 12:11, 25 January 2016 (UTC)
:I have been bold and moved the article to the title that has the least opposition. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 12:22, 25 January 2016 (UTC)
::What do you think of "Graph (discrete structure)"? — [[User:The Earwig|<span style="color:#060;">Earwig</span>]] <sup>''[[User talk:The Earwig|<span style="color:#000;">talk</span>]]''</sup> 00:00, 30 January 2016 (UTC)
:::Indeed, why not? [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 06:47, 30 January 2016 (UTC)
::::Is "discrete structure" something that a random non-mathematically-educated Wikipedia reader who gets to the disambiguation page and wants to know where to go will recognize? And isn't that reader the primary target for these disambiguators? "Discrete mathematics" at least has mathematics in it. "Discreet structure" could be a private room in a Tokyo love hotel. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 07:45, 30 January 2016 (UTC)

== New title ==
The title ambiguity problem has been solved by moving the page to [[Graph (discrete mathematics)]], but more discussion is needed before choosing the final title. Please put each proposed new title into a separate subsection to allow clean argumentation and voting. Please review the arguments (see also the [[#Requested move 5 January 2016|previous discussion]]) before voting. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:12, 30 January 2016 (UTC)

Pinging [[User:Dicklyon|Dicklyon]], [[User:kennethaw88|kennethaw88]], [[User:Joel B. Lewis|Joel B. Lewis]], [[User:D.Lazard|D.Lazard]], [[User:Slawekb|Slawekb]], [[User:Tsirel|Tsirel]], [[User:Mark L MacDonald|Mark L MacDonald]], [[User:Dmcq|Dmcq]], [[User:David Eppstein|David Eppstein]], [[User:Wcherowi|Wcherowi]], [[User:The Earwig|The Earwig]]. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:13, 30 January 2016 (UTC)

=== [[Graph (discrete mathematics)]] ===
* '''Support''', because I think that graphs are heavily used throughout this large area of mathematics, not only in graph theory. This title also makes it clear that the concept belongs to mathematics. I think that confusion with discrete functions, like sequences, is unlikely, because they belong rather to [[mathematical analysis]] than to discrete mathematics. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:37, 30 January 2016 (UTC)
* '''Weakly support''': Graph are very commonly used outside discrete mathematics (and even outside mathematics). Nevertheless, this has the advantage to clearly state that it is mathematics and that it is not about graph of functions (for almost everybody, graph of functions are graphs of continuous functions). [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:13, 30 January 2016 (UTC)
* '''Weak support'''. Nobody really knows what discrete mathematics is or whether it differs from combinatorics, but graphs are in some sense discrete so this seems vague enough to cover most of the bases and yet specific enough to disambiguate these from graphs of functions. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)
* '''Support''': Professionally I am considered a "discrete mathematician", but I have no idea of what that actually means. However, as the main function of this disambiguator is to differentiate this topic from the graphs of functions, it does the job in the least objectionable way and the general reader doesn't have to know what this "field" is in order to get that point. [[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 19:20, 30 January 2016 (UTC)
*Well, I'm not in love, but it does seem better than the current alternatives. — [[User:The Earwig|<span style="color:#060;">Earwig</span>]] <sup>''[[User talk:The Earwig|<span style="color:#000;">talk</span>]]''</sup> 19:22, 9 February 2016 (UTC)

=== [[Graph (graph theory)]] ===
* '''Weakly oppose'''. It is a circular reference and does not mention mathematics. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:37, 30 January 2016 (UTC)
* '''Weakly support''': Yes, it is circular, but one may suppose that everybody who may be interested in this article has heard of the term "graph theory" and knows that it is not about graphs of functions. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:18, 30 January 2016 (UTC)
* '''Oppose''', redundantly redundant and circularly circular. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)

=== [[Graph (combinatorics)]] ===
* '''Oppose'''. I think that graphs are used in a much wider part of mathematics than combinatorics. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:37, 30 January 2016 (UTC)
* '''Oppose''': Narrower than "discrete mathematics"; not clear that graph theory is completely included in combinatorics (topology of graphs, for example); not clear that every potentially interested user knows what is combinatorics. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:24, 30 January 2016 (UTC)
*'''Oppose'''. Too restrictive. There are too many other uses of graphs in areas of mathematics beyond pure combinatorics (e.g. in model theory, topology, group theory, etc). —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)
*'''Weakly oppose''': Although my personal favorite, I'll concede to the above points and the fact that a large segment of readers looking for this topic would have no idea of what that meant. [[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 19:20, 30 January 2016 (UTC)

=== [[Graph (mathematical structure)]] ===
* '''Oppose'''. Almost equivalent to the ambiguous [[Graph (mathematics)]]. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:37, 30 January 2016 (UTC)
* '''Weakly oppose''': not really ambiguous, but "mathematical structure" is a concept, which seems to be understood only by people having good skills in mathematics. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:28, 30 January 2016 (UTC)
*'''Oppose'''. Does not distinguish these things from graphs of functions. No better than the previous [[Graph (mathematics)]]. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)
*'''Oppose''': Ditto. [[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 19:20, 30 January 2016 (UTC)

=== [[Graph (network)]] ===
* '''Strongly oppose''': In computer science, a network is essentially a graph. Thus this title strongly suggest that this is about computer networks. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:33, 30 January 2016 (UTC)
*'''Weak oppose'''. In the intended usage, these terms are synonymous, but "network" carries the connotation of non-mathematical applications of graphs only, which I think we should avoid. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)
* '''Oppose''': While I am sure that there is a segment of editors that would have no problems with this, it just rubs me the wrong way. [[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 19:20, 30 January 2016 (UTC)

=== [[Graph (nodes and links)]] ===

* Why not? [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 09:17, 30 January 2016 (UTC)
* '''Support as proposer'''. Simple and precise, although a bit unorthodox. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:37, 30 January 2016 (UTC)
* '''Strongly oppose'''. Ambiguous, as nodes are often called vertices or points and links are often called edges, lines or arcs. One cannot guess that readers are aware of such variations of terminology. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:46, 30 January 2016 (UTC)
*: I would not call this an ambiguity. I think that you meant that a reader used to e.g. the term "vertices" may not recognize the title with "nodes" as a match. On the other hand, I would expect "nodes" and "links" to be in every commoner's vocabulary. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 17:53, 30 January 2016 (UTC)
*'''Weak oppose'''. Contradicts the more standard but more technical mathematical vocabulary of vertices and edges. Also, a node-link diagram is a visual representation of a graph, not itself a graph. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)

=== [[Graph (vertices and edges)]] ===
* '''Support as proposer'''. Just a standard maths vocabulary variant of the previous. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 20:23, 30 January 2016 (UTC)
*'''Weak oppose'''. Too [[WP:TECHNICAL]] to be a good disambiguator for naive readers. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 20:59, 30 January 2016 (UTC)
*'''Oppose'''. Confusing: May be understood as being about plotting triangles and polygons, which have also vertices and edges. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 21:52, 30 January 2016 (UTC)

=== [[Undirected graph]] ===
Narrow the scope of this article to complement the articles [[Directed graph]] and [[Mixed graph]]. Move the discussion of graph types to [[Graph theory]].
* '''Oppose'''. I think we should have an article which discusses all basic types of graphs. [[Graph theory]] should focus on applications and problems. <span style="font-family:Segoe Script">[[User:Petr Matas|Petr Matas]]</span> 09:37, 30 January 2016 (UTC)
* '''Oppose''': Readers interested in graphs do not necessarily know if their graphs are directed or not (in many texts, the distinction is only done by the context). Moreover, "undirected graph" is not proposed by our search engine when asking for "graph". [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:40, 30 January 2016 (UTC)
*'''Support'''. My preferred option. The links intended for readers who don't know or care what kind of graph they want can be changed to [[graph theory]]. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)
*'''Weakly oppose''': I initially thought this was a good idea, but on reconsideration it raises too many problems. Chief of which is that, to be useful, a reader would have to know enough about the subject already. [[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 19:20, 30 January 2016 (UTC)

=== [[Graph (connections)]] ===

I've asked Google image for "graph connections" and feel satisfied with the result. [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 15:22, 30 January 2016 (UTC)

*'''Strongly oppose''': Highly confusing title: The aim of the term between parentheses is to disambiguate. Not only "connection" does not disambiguate anything, but it is so ambiguous that even an experimented mathematician (as I am) needs explanations or context for imagining  that "Graph (connections)" refers to graphs of graph theory. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 16:26, 30 January 2016 (UTC)
*'''Oppose'''. The purpose of a disambiguator is to allow readers who don't know the subject well to figure out which of several links with similar names they should go to. This one fails that test: it is not going to work even for readers who do know the subject. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:15, 30 January 2016 (UTC)
*'''Oppose''': Meaningless. Sounds more like a social network buzz-word. [[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 19:20, 30 January 2016 (UTC)

== Path and cycle ==

There is an inane edit war going on about the definitions of path graph and cycle graph given in this article.  One editor prefers a definition in terms of connectedness and degree sequence.  In my opinion, this definition actively obscures the structure of the graph (and this is reinforced by the fact that the definition added was wrong repeatedly).  Instead, I prefer the previous definition, which explicitly gives the structure in vertices and edges.  I would like to invite other editors to give their opinions.  (Of course, both definitions offered are equivalent: they define the finite paths (or cycles).  The question is, which one is better for a broad article of this sort?) I am also open to constructive suggestions for improving the wording of the structural definition. --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 14:22, 22 January 2016 (UTC)

: The definition in terms of connectedness and degree is used in the main article on [[Path graph]] and in the litterature as well (e.g., Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006). I have never seen your definition, but you are right, they are equivalent. I suggest we use both of them.
: — [[User:Maggyero|Maggyero]] ([[User talk:Maggyero|talk]]) 14:56, 22 January 2016 (UTC).

::The characterizations in terms of connectedness and degrees are the best for verifying that a (sub)graph is a path or a cycle. However they are of little help for ''understanding'' what is a path or a cycle and why they have this name (and this is the origin of the error that I have quoted in this definition). Personally, I do not like the definition in terms of "there exists a indexing of the nodes such that", as it suggests wrongly that the verification of the definition may have an exponential complexity. The definition in term of [[graph traversal]] that I have tried (in this edit [https://en.wikipedia.org/enwiki/w/index.php?title=Graph_(mathematics)&diff=700452212&oldid=700450353]) seems therefore much better (its writing could certainly be improved). Therefore, I suggest to begin by a definition in terms of graph traversal, and to continue with the characterization in terms of connectedness and degree. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 16:42, 22 January 2016 (UTC)
:::I'm wary of definitions involving connectivity because connectivity is often defined in terms of the existence of paths (although one can instead use cuts) and we're in danger of circular reasoning. Also, we should bear in mind [[WP:TECHNICAL]]: we should work to keep our articles as readable to as general an audience as possible, and that means keeping the definitions simple, clear, and focused on the most important properties of the object in question. For instance (using a cut-based definiition of connectivity) we could define a path as a connected subgraph with no multiple adjacencieis in which, for every triple of distinct vertices, one of the three vertices disconnects the other two (puts them on opposite sides of a cut), but I think that would be unnecessarily indirect and confusing. For the same reason, I think defining subgraphs by their vertex degrees is also unnecessarily indirect and confusing (not to mention that it leads to messy special cases since it is usually a good idea to allow one vertex and no edges to count as a path). The definition I prefer is an alternating sequence of vertices and edges, starting and ending at a vertex, with an incidence between each consecutive vertex-edge pair in the sequence. (You may prefer to call this a walk, and add a condition that there be no repeated vertex in the sequence). We need both vertices and edges in the sequence: vertices because the length-zero paths have no edges, and edges to cleanly handle multigraphs. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:23, 22 January 2016 (UTC)

== redirect from »nonadjacent« ==

There is a redirect from [[nonadjacent]] to [[Graph (discrete mathematics)|Graph]] but the word does not occur in the article. Just mentioning. — Is there no bot for this? [[User:IXhdBAH|IXhdBAH]] ([[User talk:IXhdBAH|talk]]) 13:43, 6 June 2016 (UTC)

:Well, [[Graph (discrete mathematics)#Properties of graphs]] starts with "''Two edges of a graph are called ''adjacent'' if they share a common vertex.''" I guess one could just add "''...and ''nonadjacent'' otherwise.''" – [[User:Tea2min|Tea2min]] ([[User talk:Tea2min|talk]]) 14:15, 6 June 2016 (UTC)
::Instead to redirect {{noredirect|Nonadjacent}} to  [[Graph (discrete mathematics)#Properties of graphs]], I have redirected it to [[Glossary of graph theory#adjacent]], which is already the target of {{noredirect|Adjacent (graph theory)}}. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:51, 6 June 2016 (UTC)

==Assessment comment==
{{Substituted comment|length=276|lastedit=20160707124611|comment=needs more on motivation and applications. [[User:Tompw|Tompw]] ([[User talk:Tompw|talk]]) 17:20, 3 January 2007 (UTC)

Agreed. And also an extra image or two (an image is used twice at the moment) and a longer lead. [[User:Geometry guy|Geometry guy]] 16:09, 9 June 2007 (UTC)}}
Substituted at 18:19, 17 July 2016 (UTC)

== Terminology ==

{{ping|David Eppstein|Maggyero}} In addition to the widespread introduction of the nonstandard (in the context of graph theory) term "arrows" for directed edges, Maggyero's edits also widely introduced the word "link".  IANAGT, but this also seems like a nonstandard usage to me.  (It was mentioned in the article previously, but not so heavily used.)

Another thing I noticed is the following addition (my bold): "Typically, a graph is depicted in [[diagrammatic form]] as a set of dots '''or circles''' for the vertices, joined by lines or curves for the edges."  I would be more inclined to challenge this/ask for a reliable source if (1) there were any discussion of this point in the body of the article, rather than in the lead, and (2) if that discussion had any reliable sourcing.  Presumably graph theorists comment on this in their textbooks sometimes?  Maybe it (the diagrammatic/pictorial representation of graphs) even deserves a small section in this article, if it can be supported. --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 12:19, 16 April 2019 (UTC)

: (The same thing is true of the edits by Maggyero to [[graph theory]].) --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 12:21, 16 April 2019 (UTC)

:: See [[graph drawing]] for the node-link diagrams described in your other thing. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 15:26, 16 April 2019 (UTC)

::: {{ping|Joel B. Lewis|David Eppstein}} Thank you for the corrections. But in this case, is the edge set of a directed graph still denoted ''A''? (You have renamed the words "arrow" to "edge" but not the sets ''A'' to ''E''.)
::: — [[User:Maggyero|Maggyero]] ([[User talk:Maggyero|talk]]) 17:27, 16 April 2019 (UTC)

== Recent edits  ==

<small>Discussion moved from [[User talk:D.Lazard]] (begin) </small>

Your last edit Applying MOS:LISTBULLET (https://en.wikipedia.org/enwiki/w/index.php?title=Graph_theory&oldid=896700053) makes the definitions harder to read, as they do not stand out. If the definitions were less subtle it would be fine, but here this is not the case (simple graphs, multigraphs, simple graphs permitting loops, multiple graphs permitting loops, and likewise for directed graphs). So I think we should keep the bulleted version for the reader.
: [[User:Maggyero|Maggyero]] ([[User talk:Maggyero|talk]]) 09:35, 12 May 2019 (UTC)
:{{to|Maggyero}} If the definitions are hard to read, it is not because of the use or not of bulleted lists, be because a poor and confusing style. I'll begin to fix that, but only for one section, because this is a lot of work, and I have other things to do. 
:By the way, your edits are difficult to review because, firstly you do not provide edit summaries that explain the reasons of your change, secondly because you mix non-controversial minor edits (such fixing grammar and typos) with potentially controversial edits). So, please, edit only one section at a time, and explain your edit in an edit summary. If an edit would need several different explanations, then split it in several edits. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard#top|talk]]) 12:22, 12 May 2019 (UTC)

:: The current definitions are pretty clear, I put a lot of work and time into it. If you don't have time, please do nothing instead of messing with the articles. Okay for the edit summaries.
:: [[User:Maggyero|Maggyero]] ([[User talk:Maggyero|talk]]) 12:38, 12 May 2019 (UTC)

:: Thank you, this time your edits are more respectful than a mere revert, and I like the fact that you redirect to the [[Multigraph]] article so that the [[Graph (discrete mathematics)]] article can focus on simple graphs.
:: [[User:Maggyero|Maggyero]] ([[User talk:Maggyero|talk]]) 15:18, 12 May 2019 (UTC)

:: By the way, since the [[Multigraph]] article introduces 2 definitions for multigraphs (edges without own identity {{nowrap|1=''G'' = (''V'', ''E'')}} and edges with own identity {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}}), we may also do the same in the [[Graph (discrete mathematics)]] article for simple graphs (currently we only introduce edges without own identity {{nowrap|1=''G'' = (''V'', ''E'')}}), for completeness and consistency between both articles, what do you think?
:: [[User:Maggyero|Maggyero]] ([[User talk:Maggyero|talk]]) 15:29, 12 May 2019 (UTC)
<small>End of the moved discussion</small>
:::{{to|Maggyero}} In case of simple graphs, the two definitions of a multigraph coincide. So, there is no need to discuss this here. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 16:34, 12 May 2019 (UTC)

:::: What do you mean they coincide?
:::: [[User:Maggyero|Maggyero]] ([[User talk:Maggyero|talk]]) 17:14, 12 May 2019 (UTC)
:::::It may be not colloquial, but I meant "exactly the same in this case". [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 19:05, 12 May 2019 (UTC)

== Types of graph(s) ==

[[User:JayBeeEll]]:  I would like to discuss this.  Thank you for giving the reason; without that, it's impossible to know what to think (that's why I reverted your first reversion and probably why you made that first reversion).  You wrote, '"graph" is a countable noun, the plural construction is much more natural (and certainly grammatically correct)'.  I disagree with the conclusion.  The plural should appear in "types", not (necessarily) "graph".  It is good standard English to not pluralize the object of the preposition in this context.  The issue is not that "graph" is "countable" or that "graphs" is ungrammatical; it is that the plural belongs on "type" and is unnecessary on "graph", and it is good style not to pluralize twice.  [[User:Zaslav|Zaslav]] ([[User talk:Zaslav|talk]]) 22:17, 4 November 2023 (UTC)

:To me, "types of graphs" sounds more natural. <small>[rest deleted because on reflection I don't think it's making an accurate distinction]</small> —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 22:29, 4 November 2023 (UTC)
:You are asserting a general principle which is not valid in my dialect of English (which is odd because you and I grew up in the same place, albeit a few decades apart).  For an uncountable noun I would certainly not pluralize ("types of milk" means "whole, or two percent, or skim, or goat milk") but the normal way to ask a dealership whether they have sedans and hatchbacks and two-seaters is to ask what "types of cars" are available; "types of car" sounds stilted.  If you had some concrete evidence that in some other variety of English, this is an accepted rule, I suppose we could discuss what dialect the article is written in.  (Maybe "type of" / "kind of" / "sort of" are different from other superficially similar constructions?) --[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|talk]]) 22:48, 4 November 2023 (UTC)

== Revoked modifications (suspected [[WP:REFSPAM]]) ==

The modifications I recently made to this page were revoked by {{Ping|JayBeeEll}} because of suspected [[WP:REFSPAM]]. I can assure you this was not my intention, and I am not linked to any of these references whatsoever. I guess I am simply used to using much more references because I have an academic background, and the references I added are classical references used in graph theory. Would you consider reverting these modifications? I feel that they made a useful addition to the article because the link between graph and network is barely evoked even though these two concepts are practically equivalent. Similarly, I feel like mentioning random graphs could be very useful, as they are an important subfield of graph theory.
I am sorry if that violated the best practices on Wikipedia: as you can see, I am fairly new to editing and any advice on how to avoid this king of misunderstanding would be very welcome! [[User:Pylea|Pylea]] ([[User talk:Pylea|talk]]) 12:21, 23 September 2024 (UTC)

:The references you added are not good choices for the rigorous study of graph theory. The description of random graphs is wrong: there is no sense in which random graphs are antithetical to regular graphs; random regular graphs are studied all the time. It is also incorrect to say that random graphs were first studied by Erdős and Rényi without also mentioning Gilbert. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:15, 23 September 2024 (UTC)
:As I wrote over at [[Wikipedia talk:WikiProject Mathematics|the WikiProject Mathematics discussion page]] (which is a good place to ask questions!), I think the material you added was off-topic for an article that focuses on graph theory as pure mathematics. The opening paragraphs of an article [[MOS:LEDE|are supposed to summarize the material that comes after]]. Wedging in the application of graph theory to network science doesn't really work, from that perspective. Moreover, the Albert&ndash;Barabási review article is from 2002, pretty much the height of the "scale-free networks" hype era and before the people in that field were adequately scrupulous about things like testing whether a straight-ish line on a log-log plot really is a power law. [[User:XOR&#39;easter|XOR&#39;easter]] ([[User talk:XOR&#39;easter|talk]]) 22:44, 23 September 2024 (UTC)
::Okay I understand your perspective much better now. Sorry for the inconvenience, I was genuinely trying to contribute to the subject and I think I was biased towards network science. [[User:Pylea|Pylea]] ([[User talk:Pylea|talk]]) 12:43, 24 September 2024 (UTC)