What is Graph theory: Definition and 174 Discussions

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

View More On Wikipedia.org
Recent contents Top users
  1. TheMathNoob

    Proof about isomorphism (Graph Theory)

    Homework Statement 1. up to isomorphism, there is only one 2-regular graph on 5 vertices. Homework EquationsThe Attempt at a Solution I am still working on the problem, but I don't understand what up to isomorphism means. Does it mean without considering isomorphism?. I just need help with...
  2. B3NR4Y

    Graph Theory and Function Problems

    Homework Statement 1. Consider the Cartesian Product A X B, where A, B are finite nonempty sets, each with carnality greater than 1. There are two functions with domain A X B, called projections with mapping rules p1(a,b) = a and p2(a,b) = b. What is the target space of p1? p2? Are either of...
  3. B3NR4Y

    Graph Theory Notation Question

    I'm not sure if this warrants a full post, but I am doing my homework and I came across notation I'm not familiar with. Skimming the chapter it's not in there either. It says "Draw W6" but W6 has a bar over it, like complex conjugate. What does this mean? I know what W6 looks like.
  4. B

    Discrete Introductory books on Graph Theory and Combinatorics?

    Dear Physics Forum friends, I am a college junior who is currently conducting the undergraduate research in the theoretical computer science. I wrote this post to seek you recommendation on the books that separately treat the graph theory and combinatotics, both in theory and applications. I...
  5. B

    Discrete Combinatorics and Graph Theory books

    Dear Physics Forum advisers, My recent study on number theory and cryptography got me really interested in the fields of combinatorics and graph theory. I am really interested in learning about them independently now since I will not be able to take the combinatorics course until next year...
  6. H

    Bidirectional Search (graph theory)

    Attempt at solution This is an old exam question. Am I correct to say the shortest path goes through M since M is in d(O,M) and d(D,M)? I don't know how to prove this and answer the question about the cost
  7. Arsenic&Lace

    Discrete Best books on algorithmic graph theory?

    I constantly find new algorithmic graph theory problems that I need to solve as I work in research. I've learned bits and pieces from google'ing and reinvented the wheel on numerous occasions but it would be nice to get a more standard background. Network science might be more applicable...
  8. H

    Introduction to Graph Theory Book

    Helo everybody, I have buy Introduction to Graph Theory (Dover Books on Mathematics) Book from amazon... Is this book really good? See the pic : https://www.amazon.com/dp/B004TBOGPG/?tag=pfamazon01-20 http://flgopics.science/10/o.png
  9. SrVishi

    Discrete Combinatorics and Graph Theory- Harris, Hurst, Mossinghoff

    Hello, I am a student interested in pure mathematics, and am considering giving this book a try. I was wondering what you all think if this book as I have it in my possession. Is it good? If not, is there any very rigorous (I can handle Rudin Analysis rigor) discrete textbook, like one that...
  10. J

    What are some recommended books on RNA and Graph Theory?

    Hey, I'm looking for any books that contain anything on RNA and Graph Theory, was hoping if anyone has any recommendations or can at least point me in the right direction. I've already read through the section on this topic in Goodaire and Parmenter's 'Discrete Mathematics with Graph Theory'...
  11. Charles Stark

    Graph Theory Proof: Prove All Vertices of Kn Have deg(v)=(n-1)

    Homework Statement Prove that all vertices of a complete graph Kn have deg(v) = (n-1) Homework Equations ∑ deg(v) = 2|E| |E| = ½(n)(n-1) for Kn The Attempt at a Solution I may have over thought this but this was my initial path at a formal proof. Using the degree sum formula above and the...
  12. Charles Stark

    Graph Theory: Does a Graph Have Cardinality?

    So as I was beginning to read through my Graph Theory textbook I had a burning question I wanted to get some perspective on. So a Graph is defined as an object containing a Vertex Set and an Edge Set, v = # of elements in the vertex set and e = # of elements in the Edge Set (if any) Would...
  13. metapuff

    Possible Number of Vertices for Graphs with Three Edge Connections

    I want to create graphs where each vertex has three edges, and is connected by these three edges to three distinct vertices. I'd like to know the number of vertices for which this is possible. By playing around a bit, I've found that it's possible for graphs with 4, 8, and 12 vertices. If v is...
  14. P

    Can Graph Theory Predict Fossil Locations in Research?

    Im not entirely sure what section of PF this post should be in so I apologize in advance if this is not in the correct section. I don't know that much graph theory or the various fields that it can be applied to, but I do know that graph theory can be used in social media etc by using dynamic...
  15. X

    Good Books or Free Resources for Geometric Graph Theory

    I've been doing some light reading on Geometric Graph Theory, and it seem interesting to me. However, at the moment I've only managed to find a few Wikipedia articles and one .PDF of lecture notes. I'm looking for something which is more complete, such as a book or a website for example...
  16. B

    Optimizing Wi-Fi Network Frequencies with Graph Theory

    Homework Statement There are n amount of wi-fi networks in a given neighborhood. For every pair that are within 50 yards, the frequency used must be different, otherwise there will be interference. How few frequencies are required so that every wi-fi network can be assigned a frequency without...
  17. M

    Graph Theory: Extremal Problem

    Homework Statement Homework, from Modern Graph Theory by Bela Bollobas, section on extremals: 1. Suppose that G is a graph with n > r + 1 vertices and tr(n) + 1 edges. (a) Prove that for every p with r + 1 < p <= n there is a subgraph H of G with |H| = p and e(H) >= tr(p) + 1. [Hint: Try to...
  18. estro

    Can a graph with no self loops and odd common neighbors have an Eulerian path?

    I'm trying to prove that a graph with the below properties has an eulerian path. 1. Graph has no self loops or parallel edges. 2. Every two different vertices u and v have an odd number of common neighbor vertices. I'm thinking about this problem for a whole day and can't manage to prove...
  19. O

    Graph Theory - Max. Independent set algorithm

    Graph Theory -- Max. Independent set algorithm Homework Statement Design a polynomial time greedy algorithm to compute a maximum independent set for a graph. Explain the algorithm and compute T_w(n). Homework Equations The Attempt at a Solution My terse and informal...
  20. A

    Interesting graph theory problem

    I have the following problem, suppose we have a graph G of n elements, with the property that if we add one missing vertex v, we will get a complete subgraph with s elements K_s of G, in which v belongs to G'. In other words every subgraph of s elements of G is almost a complete graph except for...
  21. T

    Can Every Graph Guarantee a Minimum Matching Size?

    Homework Statement Prove that every graph G without isolated vertices has a matching of size at least n(G)/(1+∆(G)). (Hint: Apply induction on e(G)). Homework Equations n(G) = size of the vertex set of G and ∆(G)= maximum degree of v in G The Attempt at a Solution For the base...
  22. O

    Graph Theory - connection proof

    Homework Statement Prove that if a graph has > (n-1)(n-2) /2 edges, it is connected. Homework Equations ?? The Attempt at a Solution I've drawn several examples and made tables, and I can see that the graph is indeed connected if it has more edges than [(n-1)(n-2)]/2. But...
  23. M

    Graph Theory Textbooks: Bondy, Murty, Diestel, Trudeau

    Hi All, I am contemplating which graph theory text to purchase. I am stuck between a) Graph Theory by Bondy and Murty B) Graph Theory by Richard Diestel I have already been through Trudeau's intro text on my own and am looking for something deeper and more advanced. I am...
  24. T

    Proving the Even Degree Property of Vertices in Closed Trails

    Homework Statement All vertices in a closed trail have even degree. Homework Equations The Attempt at a Solution Intuitively, I know this statement is true, but I can't seem to see a clear way to show it. I know that a closed trail is a path that connects vertices, so one would follow an...
  25. T

    Can a Connected Graph with 2k Odd Vertices be Composed into k Trails?

    Homework Statement Use ordinary induction on k or on the number of edges (one by one) to prove that a connected graph with 2k odd vertices composes into k trails if k > 0. Does this remain true without the connectedness hypothesis? Homework Equations The Attempt at a Solution If k...
  26. R

    MHB Exploring Discrete Math Graph Theory Problems: A Scientist's Perspective

    I have these problems I need help with. Can anyone take a look at them? https://www.dropbox.com/s/vq8rk6z5ea5gpwd/Problems.docx
  27. B

    MHB What is the Name for a Graph with Loops That Join a Vertex to Nothing?

    Hello, Just wondering if any of you have encountered a term for a particular type of graph. It is like a graph that allows for loops, but for loops, instead of joining a vertex to itself, it joins a vertex to nothing. I just want to be consistent with existing terminology, if there are none...
  28. M

    Pathway to Learning and Research in Graph Theory

    Hi All As the title suggests I want to get to a level where I can approach research problems in Graph Theory. Specifically in the areas of Algebraic Graph Theory and Random Graphs. I know this is no small endeavour but I atleast want to put some direction into my extra studying. My...
  29. R

    (graph theory) Amount of connectivity yielding solutions?

    I have what I presume to be a basic knowledge of the terminology involved in graph theory which I will attempt to utilize in order to describe the problem in my mind. Suppose an amount of nodes corresponding to a square number is arranged accordingly, forming n rows and n columns. Each node is...
  30. A

    MHB Another tree-related graph theory proof

    Please check if my two following proofs are correct. I didn't know whether it was better to post them in a separate thread or not. I posted them together since they are both questions related to graph theory. Let me know if I should have separated them. Prove that a graph G is a tree iff it has...
  31. A

    MHB Graph theory proof related to trees

    Prove that a graph on v vertices that has no cycle is connected iff it has precisely v-1 edges. Necessary Condition: A connected graph with no cycles is a tree. Therefore, it has v-1 edges. Sufficient Condition: I need help with this. How can I use "a connected graph has no cycles iff it has...
  32. A

    MHB Graph Theory Proof: Connectivity of G Proven

    [SOLVED]Graph theory proof The graph G has precisely two vertices x and y of odd degree. A new graph of multigraph H is formed from G by adding an edge xy. If H is connected, prove that G is connected. Please check my following proof for this problem. Since G has exactly two odd vertices...
  33. S

    Recommendations for a book on Graph Theory?

    I am currently taking a combinatorics class that surveys a little bit of graph theory and it piqued my interest. Does anyone have a recommendation for a good introductory book on the subject? I am really interested in finding a book that is very readable and not the standard definition, lemma...
  34. A

    Connected Components in Graph Theory

    Homework Statement Hey guys, I have this question. Given a tree T = (V , F), find an algorithm which finds u in V, so in the graph T = (V \ {u} , F) the size of each connected component is |V| / 2 at most. What is the complexity? Homework Equations The Attempt at a Solution...
  35. G

    Graph theory vs. Diff Eq approaches towards studying complex networks

    Can anyone comment on the advantages and disadvantages of both graph theory vs. using a system of differential equations to study a complex network? For example, how much computing power and running time would a graph theory approach use compared to say solving a system of 100 differential...
  36. N

    Understanding Graph Theory: Exploring K6 and Multidesign Problems

    Hi I was reading a project description for a graph theory REU and I got stuck on a sentence I couldn't understand. Here is the description and I've bolded the part I don't get. Does this mean to remove vertices from the "other graph" until you've broken it up to G1, G2, and G3 (and maybe...
  37. Mathelogician

    MHB Some basic questions on Graph theory

    Hello everybody! I am a real amateur in Combinatorics. So please answer in the most basic way! ============================================= 1- Suppose for a graph G we have Delta=max(deg Vi : 1<=i<=n). If Delta<=2, prove that the graph G is made up of Paths and Cycles. 2- Suppose G is a...
  38. G

    Can Graph Theory Help Predict Cancer Progression?

    Let's say I had a network of enzymes that are all interconnected that may be involved in cancer progression. Each enzyme produces a chemical product that might be used by some other member in this network, but each enzyme might produce a product at different rates. Is there a way I could...
  39. C

    Interpretation on the meaning of some graph theory statements

    Hello everyone, I'm studying basic graph theory, and my instructor gives me these statements to translate into pictures. I don't quite understand the meanings of the statements, but I have some thoughts about them. 1/ "Any two vertices a, b are connected by at least 2 distinct paths of...
  40. I

    MHB Problem on Graph Theory and Algorithms

    G = (V, E) a graph with V = {1, . . . , n}. We have the function f : V → V defined f (v) = min{u|u ∈ V, dG (v, u) ≤ 2}.Demostrate that vw ∈ E(G) with f (v) != f (w) then G has the P4 subgraph induced I don;t understand what to demostrate/to do. Any advice?
  41. S

    Graph theory: Existence of cycles

    Homework Statement Let G be a graph containing a cycle C, assume that G contains a path P of length at least k between two verticies on C. Show that G contains a cycle of length at least √k. The Attempt at a Solution Since C is a cycle, there are two paths between a and b. If P...
  42. C

    Estimation for a Graph Theory problem

    I am thinking about this problem that come up in some of my work, I think this has been solved before, though I am not aware where I could find the solution. Here is the question: Suppose a graph has say 20 nodes with no edge initially, and at each instance, 4 (different) nodes are randomly...
  43. caffeinemachine

    MHB Graph Theory. Decomposition of K_{2n+1} into hamiltonian cycles.

    Theorem: Prove that there exist $n$ edge disjoint Hamiltonian cycles in the complete graph $K_{2n+1}$. ---------------------------------------------------------------------------------- I have found two constructive proofs of this over the internet. But I would like to prove it...
  44. J

    How can the sequence of tasks be represented in a graph using only 6 nodes?

    Homework Statement A house has been framed and now several jobs remain to be done. Electrical wiring must be installed, a roof must be added, drywall must be put up and it must be painted, and flooring must be installed. The electrical work must be done before the drywalling, and the drywall...
  45. W

    Graph theory - notation problem

    Hi all, I don't know if analysis is the right place for me to post this thread therefore please accept my apologies in advance if I am mistaken. In graph theory the incidence function that associates vertices & edges http://img41.imageshack.us/img41/8171/32004284.jpg , in the text it has...
  46. B

    Finding Vertex with 1 Edge in Large Graph - Algorithm

    If I have a very large graph (set of edges and vertices, NOT the "picture/sketch" of the graph), what is a very efficient way to find all the vertices with only one edge attached to them. Most of the vertices will have many edges attached to them. Also any vertex may be connected to itself...
  47. C

    MHB Problem on Graph Theory and Algorithms

    The problem is as follows: --------------------------------------------------------------------------------------------------------------------------------- Let G be a connected graph. For a vertex x of G we denote by G−x the graph formed by removing x and all edges incident on x from G. G is...
  48. G

    Graph Theory - Connectivity of r-regular graphs

    Hello everyone. All help appreciated.
  49. C

    MHB Research Prospects: Graph Theory vs Algebra

    I'm curious. Do you think that it is better to go into a subject like graph theory than it is to go into algebra, in the sense of research prospects. Graph theory, at the moment, is much much more active of an area than algebra. It seems also that going into a subject that requires you to more...
  50. G

    Is F a Subgraph of Every Spanning Tree of G If It Contains No Cycles?

    Hi everyone, Any help would be appreciated.
Back
Top