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. G

    Graph theory - complete subgraphs

    Hi everyone. I know this holds for complete graphs, I've proved that by induction. But how can I prove it for graphs which aren't complete? And what is the significance of (2n+1)/3? If a vertex has that degree, does it have some property I should immediately spot?
  2. M

    Graph theory: Embedding and genus

    Let G be a graph of genus g. Let S_g be a surface of genus g (equivalent to the Torus with g handles). The question is: If we embed G on S_g, are the faces that we obtain 2-cells (homeomorphic to disks)? I believe the answer is yes (intuitively). But, is there an argument that is more...
  3. srfriggen

    Graph Theory: Book recommendations

    (There isn't a section for Graph Theory, so I figured I'd post this in a spot where a lot of pure math topics are posted). Looking for an easy to read introduction to graph theory book to prep me for a course I'll be taking in the Spring. Nothing too simple, but nothing too in depth (as...
  4. srfriggen

    Graph Theory Book Recommendations

    I'm looking for an introductory book on graph theory. I'll be taking a course in graph theory this Spring so I don't want anything too technical, just something to get my feet wet. any recommendations for an easy to follow engaging book? A "for dummies" if you will.
  5. S

    What is the connection between hypercubes and graph theory?

    Some background: my friends love to confound me with nonsensical questions, because they know I'm the type of person who cannot let a question go, even if it has no answer, and when I arrive at one, it will be so rigidly logical that no matter how ridiculous it sounds it must be correct. My...
  6. P

    Graph Theory and Pigeonhole Principle

    A school class has 90 students, each of whom has ten friends among the other students. Prove that each student can invite three people at a restaurant so that each of the four people at the table will know at least two of the other three. If this had to be translated to a graph it would...
  7. M

    Graph Theory: Bipartite Graph Question

    Homework Statement Prove: G is bipartite iff every subgraph H has an independent set containing |V(H)|/2 Homework Equations independent set = set of mutually nonadjacent vertices. The Attempt at a Solution I am trying to understand a solution given by my prof (for the backwards...
  8. P

    Proving G Has Same Degree Vertices: Graph Theory

    Prove that if G is a simple graph with at least two vertices, then G has two or more vertices of the same degree. Pf/ Assume its true for the base case 2 vertices with no edges or 2 vertices with one edge. Then either the degree is of both is 0 or the degree of both is 1. Therefore both...
  9. I

    How Many Vertices Does a Planar Graph with Degree 4 and 10 Regions Have?

    i need some hints on how to do this problem If a connected planar graph with n vertices all of degree 4 has 10 regions, determine n
  10. J

    Maximizing Retention in Education: The Role of Reinforcement and Relevance

    When we are young we are taught about two kinds of memory. There is long term memory and their is short term memory. Students are taught to memorize facts though repetition but is repetition of a fact in a 4-8 moth period enough to retain a significant portion of that information over a long...
  11. T

    Help: Graph Theory Formula for Gzn Edges w/z & n

    z = positive int, Y = {1 2 3 ... n} where Y = n greater or equal to z defines Gzn 1)work out a formula in n and z for the edges in G zn, the vertex set to include all possible z elements subsets of Y help please what's the formula? i know how to work out the number of vertices in a formula...
  12. M

    Difference between isomorphism and equality in graph theory?

    As the title suggest, I do not understand what the difference between isomorphism and equality is in terms of graph theory. I have tried searching the internet but the few definitions I could find for each did not really shed light on the difference. I know that an isomorphism is when there is a...
  13. T

    Request for introductory book on graph theory

    I'm looking for the title to a popular introductory book on graph theory. For the best possible recommendation, perhaps it would be wise for me to give you signals of my academic maturity. I completed undergraduate math major in May 2010. Since then I've been working, but I'm looking to get...
  14. L

    Can Hall's Theorem be Applied to Solve a Matching Problem in Bipartite Graphs?

    Homework Statement Let G=A U B be a bipartite graph. For each a in A and for each b in B we have d(a)≥d(b)≥1 where d(v) is the degree of vertex v. Show that there exists a matching which saturates A. Homework Equations The Attempt at a Solution I guess I need to use Hall's...
  15. King Tony

    Graph Theory Proof Help: Connectedness and Diameter Bound in Graphs of Order n

    Homework Statement Prove that if G is a graph of order n such that D(G) + d(G) greater than or equal to n - 1, then G is connected and diam(G) less than or equal to 4. Show that the bound n -1 is sharp. Note: D(G) is the max degree of any vertex in G and d(G) is the min degree of any vertex...
  16. R

    Graph theory (matchings/connectivity)

    So my course is just getting further and further above my head. I got most of them but I'm stuck on these 3 and have no idea how to start them. This is due friday so hopefully I can get input before that! :) 1) Let G be a (2k + 1)-regular graph, and assume that G - S is still...
  17. MathematicalPhysicist

    Does G with all its degrees at least three contain a cycle with a chord?

    Let G be a graph with all its degrees at least three. Show that G contains a cycle with a chord (a chord is an edge which connects two non-adjacent vertices on the cycle). I thought of proving this by induction on the number of vertices of G, but I am stuck. Obviously, n>=4 otherwise it...
  18. R

    Characterizing Possible Sequences for Forests | Graph Theory Homework Question

    Homework Statement Characterize all possible sequences d1; d2; : : : ; dn so that there exists a forest with vertex set fv1; v2; : : : vng with deg(vi) = di. (So, you should nd a statement of the form: a sequence d1; : : : dn comes from a forest if and only if ... ) I emailed him and...
  19. P

    How do I find the number of connected components in an undirected graph?

    Need help ! – Graph Theory Hello, I have recently started studying “Graph Theory” but i find it very difficult. I'm still not good in this course. So I hope you can help me with the following task: G=(V,E) is undirected (no oriented) graph. We need to find the number of all components...
  20. N

    Proving the Existence of a Maximum-Edge Vertex in Acyclic Tournament Graphs

    Homework Statement Prove the following: If the tournament graph is acyclic, there is exactly one vertex which got edges more than any vertex in the graph. Homework Equations A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected...
  21. K

    Minimum Size of Connected Subgraph in Graph Theory | Help with u and v in G

    Let u and v be distinc vertices in a connected graph G. There may be several connected subgraphs of G containing u and v. What is the minimum size of a connected subgraph of G containing u and v? and does this suggest another question?
  22. C

    Graph Theory - bipartite related proof

    How to prove that the number of edges in a simple bipartite graph with n vertices is at most n^2/4? Definition of bipartite graph: a graph whose vertex-set can be partitioned into two subsets such that every edge has one endpoint in one part and one endpoint in the other part. I try to...
  23. R

    What Are the Potential Applications of Graph Theory in Astrophysics?

    Hi all, This is my first post to this forum, so allow me to introduce myself. I am a 28 year old person who is about to start a Phd in Machine learning with focus on graph theory. Now from my preliminary research, it seems that theory developed has a lot of use in computational biology...
  24. P

    Graph Theory: Prove Tree Has No Cycles & Adding Edge Creates Cycle

    Homework Statement Prove that a graph is a tree if and only if it has no cycles and the insertion of any new edge always creates exactly one cycle. The Attempt at a Solution Assume that a graph G is connected and contains no vertices with a degree of zero. So would I get my proof by...
  25. T

    Graph theory question- Is this correct?

    Homework Statement For any simple Graph G of maximal degree X, let U be the set of nodes that do not span any vertice in G. prove that |U| \geq \frac{n}{X+1} The Attempt at a Solution First we notice that |U| is minimized when G is X-regular, i.e. that every node is connected to...
  26. P

    Can a Simple Graph with No K5-Minor Have More Than Five Vertices?

    Homework Statement Prove that, if G is a simple graph with no K5-minor and |V(G)| Does not = 0, then G has a vertex at most 5. Homework Equations |E(G)| <= 3|V(G)| - 6 for |V(G)| >= 3 (Proved by earlier part of problem set) Handshake theorem (I don't believe we are allowed to use...
  27. M

    Graph Theory: a tree and it's complement proof

    Homework Statement The complement of T' of a tree T with n vertices has [(n-1)(n-2)]/2 edges, for all integers n greater than or equal to 2. Homework Equations Must prove using induction and using Lemma 18.2 which states "any tree that has more than one vertex has at least one vertex of...
  28. H

    Easy graph theory question: maximise sum of visited nodes

    Homework Statement Starting in the bottom left corner and moving either up or right, one square at a time, adding up the numbers along the way, what is the largest sum that can be made once you have reached the top right corner 142212 431343 214212 122331 413121 314342 211113 342322 This is...
  29. D

    [Graph theory] Formula for the size of a line graph

    Homework Statement Let G be a graph of order n and size m. V(G)={v1,v2,...,vn} and deg(vi)=ri. Find a formula for the size of the line graph L(G) in terms of n, m, and ri. Homework Equations The http://en.wikipedia.org/wiki/Line_graph" L(G) is the graph such that every vertex in L(G)...
  30. A

    Help Needed: Graph Theory Assignment on Vertex Colouring

    I am working on graph theory assignment. I need help because I am not seeing where I am going with this question. Here's the question: G is a simple graph with n vertices. -> show that vertex colouring of G [ X(G) ]* vertex colouring of G complement >= n -> show that the vertex...
  31. T

    What is a cycle in graph theory

    Homework Statement Sorry about the basic question, I haven't takena course on graph theory yet but need this for a course in computer science. The problem: Write a program whose input is an adjecancy matrix and whose output is the number of cycles of length 3 and 4. The Attempt at a...
  32. Q

    Courses Is graph theory an interesting option course?

    I'm in my 4th year of a physics program, and I've got some serious freedom choosing courses now. Has anyone taken graph theory? I've got a basic idea what it is, but no clue how difficult it might be. Any other good math courses to take as an option that won't bee too difficult? For...
  33. G

    Graph Theory and Bipartite graphs

    I have a problem involving graph theory. This is not a graph theory course though so I do not know much about it. If we have complete bipartite graphs consider whethere or not they are graceful. A graph is graceful provided the vertices of the graph can be assigned v distinct integers...
  34. D

    Prove Graph Theory: All Vertices > 4, At Least 12 Degree 5

    Homework Statement If all vertices of planar graph have degrees greater than 4, prove if that graph has at least 12 vertices with degree of 5. Homework Equations d1+d2+...+dn= 2*m (m - number of edges, di-degree of i-vertex) f=2-n+m, f - number of faces, n-number of vertices The...
  35. A

    Graph Theory: Pure or Applied?

    Hi Is graph theory a more pure or applied subject? I thought it was pure but now I am confusing myself because it has so many applications. Thanks
  36. F

    Why is this the obvious? (graph Theory)

    http://www.win.tue.nl/~aeb/srgbk/node10.html Under the 'For connected graphs all is clear from above' I've been asked to prove this for connected graphs, but I don't see how this is so clear? Can anyone help me? Thanks
  37. J

    Graph Theory: Complement of a Graph

    I'm wondering, is it possible a graph G and its complement G' to be complete?
  38. M

    Mathematica Mathematica, Matrices and Graph Theory

    Hello I imported a 30 X 30 matrix into Mathematica. I made a graph out of this and then found the minimum spanning tree. Next, I printed off a list of the edges. I included the edgeweight option to get the associated weights listed next to each edge. My goal was to ultimately sum these...
  39. B

    Graph Theory Proof: Number of Vertices and Edges in a Connected Graph

    Homework Statement Let G be a graph with at least two vertices, such that the cut induced by every proper nonempty subset of vertices of G contains exactly two elements. Determine (with proof ) the number of vertices and edges in G. Homework Equations Connectedness. A graph G is...
  40. D

    How Do You Calculate the Size of a Line Graph in Graph Theory?

    Homework Statement Let G be a non-empty graph of order n whose vertices have degrees d1, . . . , dn. The line graph of G is defined as follows: the vertices of L(G) are the edges of G, and two vertices of L(G) are adjacent if they share an endpoint in G. Prove that the size of L(G) is...
  41. V

    Is Every Induced Subgraph with a Cut-Vertex a Block?

    If G is a connected graph with a cut-vertex v and G1 is a component of G-v, then show that the induced subgraph <V(G1)U{v}> of G need NOT be a block of G. I guess all I would need is a counterexample, but I can't come up with one.
  42. ╔(σ_σ)╝

    Discovering Graph Theory: Is it Worth Taking for Rigor and Interest?

    I am planing to take a course in Graph theory at my university, but i have no idea what it is. I want to take something that is ,to some extent, rigorous and interesting. This is the course summary provided by my school : Introduction to graph theory and its applications with an emphasis on...
  43. A

    Graph Theory Question: Finding Equal Degree Vertices in Graphs

    Homework Statement Hello everyone; This is the problem that I am working on: (a) - Show that in every graph there are two vertices of the same degree. (b) - Determine all graphs with exactly one pair of vertices of equal degree. Homework Equations None. The Attempt at a...
  44. D

    I need a second opinion on a Graph Theory proof.

    First and foremost, let's get something straight before I post my proof: I'm not enrolled in any classes. I don't have any class money. Though my grades were strong enough for grad school, I don't think I would've made a good mathematician. I'm just not good enough. I thought I was done with...
  45. E

    Graph Theory Help: Finding # of Graphs w/ n Vertices & k Edges

    The graph theory HELP! How many distinct graphs can be found by the set V={1,2,...,n} with k edges? For this question i conclude that totao.l number of distinct graphs comes with 2^(choose two in n) but i cannot find the solution which gives the relation with k edges can you help me?
  46. S

    Proof of Degree 5/6 for Graph Theory: Pigeonhole Principle

    [b]1. Suppose a graph has nine vertices each of degree 5 or 6. Prove that at least five vertices have degree 6 or at least six vertices have degree 5. Homework Equations [b]3. I'm pretty sure that I need to use the Pigeonhole Principle to solve, but don't know where to go from there.
  47. G

    Graph Theory Terminology: Vertices, Edges, Endpoints

    I was wondering if I could get some help with the terminology when it comes to graph theory. In this picture : http://en.wikipedia.org/wiki/Image:6n-graf.svg the numerical values are vertices (or nodes as some call it), so what are the edges then (are they the lines that connect the nodes)...
  48. F

    Proving Even Cycle in Graph Theory with 3 x-y Paths

    Hello! This question seems simple but I think I'll need your help to prove it. Prove that if there are vertices x and y in V(G) such that G contains three independent x-y paths then G contains an even cycle. Thank you in advance.
  49. M

    How Can Induction Be Used to Prove Paths in Graphs with Odd Degree Vertices?

    prove : Let G be a graph that has exactly 2k vertices of odd degree. Show that there are k edge-disjoint paths each of which joins a different pair of ver- tices of odd degree. I have to prove this with induction on k. There is a hint that I need to strenghten my induction hypothosis but I...
  50. S

    Graph Theory proof via induction

    Homework Statement Prove by induction that the graph of any triangulation of a polygon will have at least 2 vertices of degree 2 Hint: Split the triangulation graph into 2 triangulation graphs at some chord e The Attempt at a Solution Ok I am pretty terrible at induction proofs...
Back
Top