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

    I Find Smallest Subtree of G w/ Nodes from S

    I have a unique problem and looking for a known fast algorithm for it. I have an unweighted but directed graph `G`. I then have a subset collection of nodes `S` existing in `G`. I want to find the minimum sub tree in `G` such that it contains all the nodes in `S`. I so far found Chu-Liu/Edmonds...
  2. feesicksman

    Find the total number of ways of coloring the eight regions

    The eight regions
  3. cianfa72

    I Circuits or edge-disjoint unions of circuits in a connected graph

    Hi, I've a question related to the graph theory. Take a connected graph with ##n## nodes and ##b## edges. We know there are ##m = b - n + 1## fundamental circuits. Which is the total number of nonempty circuits or edge-disjoint unions of circuits ? If we do not take in account the circuit...
  4. C

    I Number of edges in a tree digraph

    I know that if an undirected graph is a tree then its number of edges satisfies ## |E| = |V| - 1 ##. If a directed graph ( digraph ) is a tree, is the result also true? ( I can imagine just taking an undirected tree and making its edges directed but this is specious since it's a little bit more...
  5. M

    Spectral Graph Clustering: where does the 'scoring' function come from

    Hi, I was reading through some slides about graph clustering. In the slides was a very short discussion about 'eigenvectors and segmentation'. I don't quite understand where one of the formulae comes from. Context: We have some undirected graph with an affinity matrix (i.e. weighted adjacency...
  6. B

    Sudoku solver by graph coloring theory

    Hello everybody! I have to implement a sudoku solver in C ++ taking advantage by graph coloring theory, where each number to insert is a color of the associated graph node. In particular I would like to use the Welsh-Powell algorithm. I find myself in trouble starting with this project and I...
  7. C

    Showing existence of an Edge s.t. Graphs T1' , T2' are Trees

    Attempt - I am stuck at this problem for hours, couldn't make any progress. Still, here's what I've done : Let ## e_1 \in E_1 \setminus E_2 ## be arbitrary. Suppose for the sake of contradiction that ## \forall ## ## e_2 \in E_2 \setminus E_1 ##, ## T_1' = \langle V,(E_1\setminus \{ e_1 \})...
  8. B

    Find an Interesting Topic in Graph Theory for an Exam

    Hello everybody, I hope it is the right section to post. For an exam, I should delve into a topic concerning graph theory. My work should include theoretical explanation, pseudo code, correctness analysis, complexity analysis and code implementation (C ++, python or other). Could someone...
  9. seel

    Combining Graphs: Finding Solutions through Graph Homorphisms

    We are working on an architectural project using graphs and we are looking for a way to combine separate graphs into one. We looked into methods to generate graph homorphisms, following the maximum graph homomorphism (MGH) (Langberg et al. 2006) and Paweł Rzążewski’s Exact Algorithm (2014)...
  10. D

    MHB How to get started in algorithmic graph theory?

    Hi, I read a book on graph theory by West and is interested to learn algorithmic graph theory now.What algorithms are important in algorithmic graph theory in all fields such as planarity detection,1-factor ,hamiltonian cycle detection,finding eulerian tour,greedy coloring,graph realization
  11. S

    I Finding if a subgraph of a minimal non-planar graph is maximal planar

    Given a minimal non-planar graph G, we need to find out if G', which is G-e, where e is a removed edge, we need to prove that there exists an edge e such that its removal would make G' a maximal planar graph. My idea in trying to figure this out would be by taking a minimal non-planar graph and...
  12. S

    I Finding the chromatic number of a graph with biconnected components

    Our problem involves a graph G that is simple and connected, where every biconnected component is a cycle that has at least four vertices in it. The maximum number of components we can get from removing a cut vertex is 4, and we are asked to find tight bounds on the chromatic number of G. My...
  13. S

    I Question regarding degrees of a graph and its biconnected components

    The problem is for us to consider a biconnected decomposition, and that proof for a graph, the degrees of all the vertices in a graph is even iff the degrees of all the vertices in all of its maximal biconnected components is even For solving that if the degrees of all the vertices in the...
  14. J

    MHB Exploring Graph Theory to Identify Network Similarities

    Hi, I am very new in Graph Theory, and am currently trying to figure out it's potential to solve my research problem. Here it goes: I have a large physical network (10000 nodes, around 14,000 edges), it can be represented by an undirected weighted graph. Many portions of the network might have...
  15. S

    I  Find Two Equal Length Paths in a Tree Graph

    In order to try and sovle this problem, my idea here was to use an extremal argument, with two equal length maximum paths on a tree. I said that no matter where the two graphs started, they'd end up having to cross paths since if there were two distinct paths with equal lengths the graph would...
  16. S

    Prove the decomposition of a graph w/ even edges produce a 2-path set

    For my base case I just used a graph with three vertices and 2 edges. Decomposing this would just give us the same graph, which has a path length of 2. The inductive step is where I'm having some trouble: One idea I have is that we take a graph G then inductively remove an edge to create two...
  17. S

    I Prove that a given graph contains a cycle using induction (Graph Theory)

    My Problem: Given a Graph G = (V,E), where the number of vertices is less than or equal to the number of edges, use induction to prove that the graph contains at least one cycle (the graph is not required to be completely connected). My attempt: For my base case, I used only one vertex with one...
  18. N

    I What is the Cheapest Route to Visit 6 Destinations in Tokyo?

    Hello, recently I was looking into visiting Tokyo and started looking into its complicated but wonderfully efficient railway system. I picked 6 destinations in the area and looked up how much it would cost to go from anyone of the locations to any other. Then I started to wonder, if I...
  19. Mr Davis 97

    I Understanding a Graph Theory Proof

    Prove that if a simple graph G has 6 vertices then G or its complement has a subgraph isomorphic to ##K_3##. The proof begins by noting that is must be the case that G or its complement as a vertex with degree at least 3. Why is this the case?
  20. Iliody

    I Question about a definition in Rivasseau's book

    I have a problem understanding a definition at page 93 of 'from perturbative to constructive renormalization', that is related to Graph Theory, and he uses it on the proof of the uniform BPH theorem for \phi_4^4 (\lambda \phi^4 in D=4). You have a graph G, a forest of quadrupeds F, and g a...
  21. J

    Number of possible trees in graph theory

    Homework Statement Homework Equations Reduce the matrix to reduced matrix by removing 1 row completely Number of trees = determinant of [ Ar times ArT ] The Attempt at a Solution I removed 4th row to get Ar(reduced matrix) Then I did Ar times Ar (transpose) And found it's determinant but I...
  22. F

    I Use of irrational numbers for coordinate system

    Why should a person prefer irrational coordinate system over rational? My friend stated that its because most lines such as ##y=e## cannot be plotted on a rational grid system. But that cannot be true since ##e## does have a rational number summation ##2+1/10+7/100...## which can be utilised to...
  23. Auto-Didact

    A Algebraic topology applied to Neuroscience

    Eugene Wigner once famously talked about the "unreasonable effectiveness of mathematics" in describing the natural world. Today again we are seeing this in action in particular with regard to the description of the biological brain from the perspective of neuroscience. Researchers from the Blue...
  24. maverick_starstrider

    I Spectral Bisection of Simplest Graph Clearly Incorrect

    I'm playing around with Spectral Bisections and Fiedler vectors as ways of bisecting a graph using the sparsest cut. However, I'm finding that even the most trivially simple graphs are bisected incorrectly by this approach. What am I missing? Take for example a graph that is just a 4x4...
  25. T

    I I would simply like to know how to get 2^k.

    The complete graph K_n can be expressed as the union of k bipartite graphs iff n≤2^k I would simply like to know how to get 2^k.
  26. T

    Discrete Graph Theory book or literature that dives into these concepts

    I need recommendations on literature to read. Basically i do not understand these section of Frank Harary's book on graph theory since the definition of what a boundary and a cycle vector is not clearly defined. I have googled literature on it but I am having a tough time finding the right...
  27. Edward Vogel

    I Representing Tiling and Packing Solutions

    I have been long interested in how one might find all of the 240 unique solutions to the SOMA cube puzzle since receiving one for Christmas in 1968. If one were to find all of the solutions (many of them are "similar" and there is an interesting variety "similar" to boot) . . how best to...
  28. P

    MHB Understanding Two Graph Theory Problems

    Hi! I'm struggling with these two problems: 1. If for whichever two vertices a and b in the graph G there is only one simple path from a to b, then the graph is a tree. Eh... isn't this part of the definition for a tree? I really don't even know where to start with proving this statements...
  29. T

    I The largest n such that K_n can be expressed as the union of

    there's a proof provided, but i want to know the intuition as to why it is 2^k.
  30. P

    Graph theory, rank and other characteristics

    Homework Statement hello, I have this graph and i have to figure out these so to speak characteristics. 1) find incidence matrix 2) arrange peak according to rank and layers 3)draw new arranged graph 4) find new connection matricies of peaks and arcs Homework EquationsThe Attempt at a...
  31. T

    I Graph Theory: I understanding the corollaries

    please check the attached photo
  32. T

    How to construct a graph with girth = twice the diameter + 1

    Homework Statement I am trying to verify this theorem for myself. Theorem: Every graph G containing a cycle satisfies g(G)≤2diam(G)+1 Homework Equations N/A The Attempt at a Solution i have drawn graphs and i failed to verify the theorem. is it even possible, since increasing the girth...
  33. T

    A Every graph GG containing a cycle satisfies g(G)≤2d+1

    Proof: Let C be a shortest cycle in G. If g(G)>= 2diam(G) + 2, then C has two vertices whose distance in C is at least diam(G)+1. Question: why is it at least diam(G)+1? cont. of proof: In G, these vertices have a lesser distance; any shortest path P between them is therefore not a subgraph of...
  34. H

    MHB Optimal Seating Arrangement Algorithm for Friendship Graphs

    Hi all, I am struggling the question, please see attachments. Thanks a lot Devise an algorithm which, given a (directed) friendship graph (in the xkcd format), finds the optimal seating arrangement. Your algorithm should include the following:  a description of the required input format...
  35. N

    Graph Theory Reconstruction Conjecture

    Hello all, I recently starting studying graph theory in my free time and have become very interested in the Reconstruction Conjecture. Since I am new on the subject I am not sure where to start my search for additional information/insights/papers on the topic, I thought I would ask here for...
  36. U

    C - Degree of a directed unweighted graph

    Homework Statement Given the representation of directed unweighted graph: typedef struct { int n;//num. of vertices void *info[MAX];//information of vertices int am[MAX][MAX];//adjacency matrix }GRAPH; Write a function int minDegree(GRAPH*); and int maxDegree(GRAPH*); that return the...
  37. D

    Courses Should I take geometry or graph theory for elective?

    I just want something easy to boost my gpa and these are my two options. The geometry course is euclidean not topological. Thanks
  38. L

    I Graph Theory: (proof)conditions for Euler Circuit in Digraph

    I have read in many places that one necessary condition for the existence of a Euler circuit in a directed graph is as follows. Theorem: "A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree." However, I don't understand...
  39. TheMathNoob

    Proving Graph Theory with Group Permutations | G = Sn and S Set

    Homework Statement The problem is attached. I don't get this part. Let G = Sn be the group of all permutations of S. S is a set, so how can we permute something in a set?. Neither I know if the 4 power in the S is a typo. Homework EquationsThe Attempt at a Solution
  40. TheMathNoob

    Automorphism proof (graph theory)

    Homework Statement The problem is attached and it's part A. There is no need to put problem 4 hence the problem is fully explained in the file attached Homework Equations Zk is mod k basically. The Attempt at a Solution I know that we have to prove that the transformation is onto,one to one...
  41. G

    Proof of NP-completeness via reduction

    Homework Statement You are given some undirected graph G = (V, E), along with a set S which consists of 0 or more pairs of G's edges. As an example, a complete graph on 3 vertices (a triangle, basically) would be described as follows: G = (V, E) = ({v1, v2, v3}, {v1v2, v2v3, v1v3}). A set S...
  42. TheMathNoob

    Hall's theorem problem (graph theory)

    Homework Statement Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3...
  43. ff4ever

    What does it mean? (Graph theory)

    Hi, In the paper "A triangle-free circle graph with chromatic number 5" from A.A. Ageev, I don't understand what the author mean with the following definition: Somebody can explain it to me? (I'm not mathematician). Thanks ! Link to the whole paper...
  44. U

    Graph Theory: Finding the number of vertices

    Homework Statement 1. How many vertices will the following graphs have if they contain: (a) 12 edges and all vertices of degree 3. (b) 21 edges, three vertices of degree 4, and the other vertices of degree 3. (c) 24 edges and all vertices of the same degree. Homework Equations "Theorem 1 In...
  45. TheMathNoob

    Graph theory (incidence matrix and linear algebra)

    Homework Statement I can't understand this paper. I understand the whole incidence matrix stuff, but I don't quiet get how it relates to the linear algebra. I don't know if this is allowed to do, but I will ask you questions line by line, so basically you will read the paper with me explaining...
  46. TheMathNoob

    Graph theory proof (Unlabeled trees)

    Homework Statement A. Show that n^n−2/n! < T(n) by looking at how the symmetric group Sn acts on labelled trees. Use |Sn| = n! T(n) is the number of unlabeled trees on n vertices Homework EquationsThe Attempt at a Solution I can't find any mathematical relation between labelled trees and...
  47. TheMathNoob

    Proving a Cycle Exists in Finite Graphs with Degree 2+ Vertices

    Homework Statement Exercise 0.1. Suppose that G is a finite graph all of whose vertices has degree two or greater. Prove that a cycle passes through each vertex. Conclude that G cannot be a tree. Homework EquationsThe Attempt at a Solution If every vertex in a graph G has degree two or...
  48. TheMathNoob

    Proving a Tree is a Minimally Connected Graph in Graph Theory

    Homework Statement Let G be a connected graph. We say that G is minimally connected if the removal of any edge of G (without deleting any vertices) results in a disconnected graph. (a) Show that a connected, minimally connected graph has no cycles. (b) Show that a connected graph with no cycles...
  49. TheMathNoob

    Does Induction Work for Proving Graph Theory Statements?

    Homework Statement Prove that a complete graph with n vertices contains n(n − 1)/2 edges. Homework EquationsThe Attempt at a Solution The solution gives and inductive proof, but I am just wondering if this works as well. If we have a set of n vertices or points and we try to match all...
  50. TheMathNoob

    Proof about isomorphism (Graph Theory)

    Homework Statement 1. Prove or disprove up to isomorphism, there is only one 2-regular graph on 5 vertices. Homework EquationsThe Attempt at a Solution I am making this thread again hence I think I will get more help in this section old thread...
Back
Top