Graph theory Definition and 175 Threads

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. 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...
  2. T

    Proving |V(G)|-1 <= |E(G)| for Connected Graphs: Graph Theory Homework Statement

    Homework Statement Show that for any connected graph we have the |V(G)|-1 <= |E(G)| The Attempt at a Solution There exists a longest path in the connected graph, call H. It has |E(H)|+1>=|V(H)|. For the other parts of the graph, in order to minimise the number of edges we have all other...
  3. T

    Can Graph Theory Exist Without Visual Graphs?

    From the definition of a graph, it dosen't mention anything about a pictorial graph. Things are only dealt with set wise so it is possible to do graph theory without graphs? It would be extremely unnatural though.
  4. D

    Research Topic in Graph Theory or Non-Well-Founded Set Theory

    I'm doing to come up with a subject in either of them to do either an "independent study" or "project" on, the former is a course which simply requires you to learn the subject and the latter is "independent study" + a x-page paper. Unfortunately I don't know either subject too well so I can't...
  5. E

    Graph Theory Problem: Proving Dual Graph Faces Contain 1 Vertex

    Homework Statement http://en.wikipedia.org/wiki/Dual_graph I am trying to show that if a graph G is connected, then each face of its dual graph G* contains exactly one vertex of G. Homework Equations The Attempt at a Solution I tried counting the vertices in G and the faces in...
  6. D

    Graph Theory Problem: Nonisomorphic Connected Graphs with 5 Vertices and 4 Edges

    Hi! I was given the following task: Homework Statement (a) Exhibit three nonisomorphic, connected graphs with five vertices and four edges. (b) Argue that every connected graph with five vertices and four edges is isomomorphic to one of the three in part (a). The Attempt at a Solution...
  7. D

    Solving 5V 4E Graph Theory Problem

    Hi! I was given the following task: It's not very difficult to draw the graphs: http://i83.photobucket.com/albums/j315/dobry_den/graphs.jpg but i can't think of how i would argue... Do you have any idea? Thanks in advance!
  8. MathematicalPhysicist

    Kirchoff theorem in graph theory

    i read a little bit of the syllabus in my university graph theory course and i just wonder if the the kirchhoff theorem in graph theory has any application to kirchhoffs law in direct current in electricity?
  9. B

    Discrete space <-> graph theory

    My complete layman's question. In two of Smolin's books as well as in popular science journals I read that there is the idea of a discrete space, i.e. space would not be completely continuous but rather have "smallest pieces". I wonder if this means that space can be modeled as a graph (the...
  10. B

    Graph theory and simple circuit help

    Hi, I have this problem I don't understand I have been on it for days now: Show that the existence of a simple circuit of length k, where k is a positive integer greater than 2, is an isomorphism invariant. please can someone help me with it? Thank you B.
  11. B

    Proving Connectedness of Cycle Graphs: An Alternative Approach

    I remember when I was taking discrete analysis of data structures and we had to prove certain graph theory properties. I'll give a specific example, prove that the cycle graph, C_n, is connected for all n. From what I remember, it was induction we used to prove this...what I want to know...
  12. JasonJo

    Graph Theory Problems: Polygonal Guarding in Simple Polygons with g(P) = 2 and 3

    These questions deal with polygonal guarding: a) Suppose P is a simple polygon where g(P) = 2. Prove or disprove that P can always be guarded by two guards that can always see one another (ie the definition of visibility, but not clear visibility) To disprove all is needed is a...
  13. A

    Graph Theory - How do I construct this graph?

    Graph Theory -- How do I construct this graph? I have a question which I think I'm supposed to solve using graph theory. Here's the problem statement: "Given 6 people, suppose that the relationship between them is that they are either friends or complete strangers. Show that there must be...
  14. V

    Graph Theory & Its Applications Explained

    Can anyone explain to me the graph theory and its applictations.
  15. JasonJo

    Can a knight make every possible move on an 8x8 chess board exactly once?

    a professor posed the following question in class: Is it possible for a knight to move around an 8x8 chess board so that it makes every possible move exactly once? (consider a move between two sqaures connected by a knight to be completed when the move is made in either direction) so i...
  16. JasonJo

    General Help for Combinatorics and Graph Theory

    hey guys I am taking a class right now called Finite Mathematical Structures, and I am having a pretty tough time. although it's only about 1 - 2 weeks into the semester, i am having a hard time actually understanding graph theory problems. so far we are doing isomorphisms, edge coverings...
  17. P

    Proving Uniqueness of Graphs with a Given Degree Sequence

    Hey everyone, I wasn't sure where to put this, since graph theory doesn't really have it's own name here (we don't even have a combinatorics or discrete math category...), so I decided to just put it here in "General Math". My question pertains to degree sequences of graphs. I'm asked to...
  18. M

    What are the properties and connections between bit strings and graph theory?

    I am not really sure how to start this problem, and I have tried searching everywhere. If you could help me that would be great...just to know how to get started. I'm in 2nd Year, Intro to discrete mathematics, if it matters. Thanks Let G be a graph whose vertices correspond to the...
  19. J

    What Is the Difference Between a Subgraph and an Induced Subgraph?

    what's the difference between a subgraph and an induced subgraph? looking here: http://mathworld.wolfram.com/InducedSubgraph.html how is the figure K8 ? isn't that K10 ?? also, what is a spanning subgraph?
  20. Reshma

    Proving Non-Trivial Trees Have At Least 2 Vertices with Degree <2

    I'm not sure where to post this, but anyway here is the question: Given a graph G(p,q) is a tree where p is the number of vertices and q is the number of edges. Since given graph is a tree, number of edges q=p-1. How do you prove that every non-trivial tree has atleast two vertices with...
  21. N

    Help! I'm Struggling with Graph Theory Exam!

    I'm having an exam on graph theory next week and I'm having some problem with understanding the meaning of calculating eigenvalues of adjacency matrices for graphs. My notes suck from the lectures and I'm totally lost... Our professor asked "What is the sum of elements in row k of the...
  22. W

    Graph Theory: Dijkstra's Algorithm

    Hello, Does anyone know of an online resource which explains Dijkstra's Algorithm both in tabular form and graphical form? My text does an incredibly poor job explaining this algorithm. I sort of understand it graphically. But I have absolutely no idea what is going on when it comes to...
  23. W

    Intro Graph Theory: Components Connectivity

    Hello, I am having trouble understanding the definition of components and connectivity. Here is the definition I have been given in my text: Alright, I know that a subgraph is a subset of vertices and edges which itself forms a graph. I also know that a path is a subgraph in which no edge...
  24. W

    What are the definitions of graph theory and its components?

    Hello, My discrete math course has begun a section on graph theory. And I am hung up on some of the definitions. If someone is familiar with graph theory, I would appreciate it if some of these definitions could be reworded in another way. I will post the definitions we have taken so far and...
  25. V

    Can Greedy Coloring on Chordal Graph Complements Be Proven Optimal?

    does anyone have an idea on proving that there is a triangle-free k-chromatic graph for every positive integer k? or, how to prove that given a simplicial ordering on a chordal graph G, running the greedy coloring algorithm on the reverse order gives the optimal coloring on the complement...
Back
Top