# Should we merge “graphs” with “graph-theory”?

The tags and seem to cover much of the same ground.

Should we merge them?

• We discussed this a long time ago but didn't come to a solid conclusion. – Gilles 'SO- stop being evil' Dec 12 '18 at 7:52
• I don't think they're synonymous, but people are bad at tagging. – Raphael Dec 12 '18 at 18:19
• Can you give an example of the difference? – Yuval Filmus Dec 12 '18 at 18:31
• Off the top of my head, two types of questions come to mind: 1) complexity-theory+graphs such as "Is this problem similar to Vertex Cover also NP-complete?".You'd ask a complexity theorist about that, not a graph theorist. 2) algorithms+graphs/modelling+graphs -- if it's about modelling a domain problem using graphs and then solving the problem using textbook algorithms, you don't delve into graph theory per se. You're using graphs as a tool. (Of course, this is a question of semantics, and yes, there are overlapping areas of expertise.) – Raphael Dec 27 '18 at 14:40
• For me, graph theory is about the structural properties of graphs; a usual theorem is not bothered with algorithms or computational problems. – Raphael Dec 27 '18 at 14:43
• Your two examples are both appropriate for the graphs tag. My conclusion is that questions on graph theory just don’t belong here. Questions such as the number of leaves in a complete binary tree (hardly deep graph theory as well; more like discrete math) are more suitable for Mathematics. Perhaps we should add a graph algorithms tag? – Yuval Filmus Dec 27 '18 at 14:44
• Based on the positive consensus here, I was about to do the merge... but I want to check if we have consensus on the direction of the merge. We're getting rid of graph-theory and keeping graphs? Do I have that right? – D.W. Oct 17 '19 at 21:46
• I don't have strong feelings either way. Someone has to make this arbitrary decision, it might as well be you. – Yuval Filmus Oct 17 '19 at 22:06
• Done! I have merged them. – D.W. Oct 20 '19 at 18:54

+1

I would say applications of graphs in CS do not fall in under graph theory as a mathematical field (research area), e.g. all the A* questions should be labeled graph.

On the other hand, questions regarding graph classes and their complexity (recognition, modification, operations etc.), as well as classical problems like chromatic number etc., should possibly be graph-theory.

That said, the distinction is rarely interesting here at cs.sx.

Therefore I vote yes: merge.

+1

From Wikipedia,

... graph theory is the study of graphs, ...

I don't think there is any difference between "graphs" and "the study of graphs".