Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
0answers
123 views

Number of paths through an incomplete graph (with restrictions)

Here's a question I came upon while fiddling around with yarn on spindles. I joined three spindles so that they were orthogonal.. then, beginning at the base of a particular spindle (A), wound it ...
3
votes
1answer
72 views

If $A$ is the adjacency matrix of a graph, why does the $(i,j)$ entry of $A^n$ give the number of $n$-step walks from $i$th vertex to $j$th vertex?

Let $A$ be the adjacency matrix of some directed graph with $m$ vertices labeled as $v_1, v_2, \ldots, v_m$. So here $A_{ij} = 1$ if there is an edge from $v_i$ to $v_j$, and $A_{ij} = 0$ otherwise. ...
0
votes
1answer
88 views

Is there a database of cubic graphs on the web

I'm doing a research project in graph theory and need to program some stuff to help me study it. I used to have access to Mathematica but now I don't. So, when I'm programming things I'm entering the ...
1
vote
0answers
41 views

On graph homomorphism properties

Let $G,H$ be finite graphs with $|V(H)| > |V(G)|$. Let $\mathcal{f}:G\rightarrow H$ be an injective homomorphism - that is, $\mathcal{f}$ is: $1.$ Injective - ...
0
votes
1answer
100 views

Characterizing trees where every diametral path shares an edge

In a graph $G$, a diametral path is a path of length $\text{diam}(G)$ joining two vertices that are at a distance $\text{diam}(G)$ from each other. Given a tree $T$, consider the set of all diametral ...
1
vote
1answer
119 views

Prove that these lines are perpendicular (orthogonal)…

According to the Law of mathematics, the product of slopes of $2$ perpendicular lines has to be $ -1 $. Then, how do you prove that the following lines are perpendicular. $x=4$ , $y=6 $ My ...
0
votes
2answers
2k views

Proving a connected graph is a tree if the DFS and BFS traversals from the same node are equivalent

Let $G$ be a connected graph and $v$ be a vertex in $G$. Suppose a DFS traversal from $u$ is performed resulting in a tree $T$, and a BFS from $u$ also results in the same tree $T$. I would like to ...
0
votes
1answer
65 views

biconnected components in a graph

i just started going through biconnected components can someone explain me this Show that if G is a connected undirected graph, then no edge of G can be in two different biconnected components
0
votes
1answer
26 views

Graph divisibility problem [duplicate]

For $p$ and $q$ distinct primes. Two conditions are given: vertices of graph $G$ are integers in the set $\{0, 1, 2, \ldots, pq-2, pq-1\}$; there is an edge of graph $G$ between $a$ and $b$ if $ab$ ...
1
vote
1answer
28 views

Number edges of 3-regular graph so that every vertex has a 0,1, and 2 edge

Let's say you have a graph such that every vertex has exactly 3 edges. You try to number every edge of the graph with either a 0, 1, or 2 so that every vertex has exactly one of each type of edge. Is ...
1
vote
1answer
86 views

MAGMA: Retaining original vertex set

I am trying to work with graphs in MAGMA, but to my surprise I noticed that the vertices of the graph are no longer considered elements of the set I started with. Here is an example: X:={1.. 13}; ...
0
votes
1answer
400 views

How to determine if a sparse matrix is structurally symmetric

Say you have a sparse matrix in CSC or CSR format (or whatever format is suitable for this to work) and all you know are it's dimensions: $n$, $m$ and $nz$, and the data in the structure. You are told ...
2
votes
1answer
103 views

Converse of the Euler's formula for planar graphs

Let $G=(V,E)$ be a planar graph. Suppose a planar representation of $G$ has been chosen and that $$v-e+f=2,$$ where $v,e$ and $f$ are the number of vertices, edges and faces respectively. See ...
0
votes
1answer
154 views

Example of Exponential Graph

Given a definition below (source: On Hedetniemi's Conjecture and the color template scheme by C. Tardiff and X Zhu): The exponential graph $G^H$ has all the functions from vertex-set of $H$ to that ...
0
votes
1answer
38 views

Is it true that every scc is the union of cycles

If $S$ is a strongly connected component of a digraph, then $S$ is the union of cycles of it's vertices, I conjecture. Is this true? I can nowhere find such a statement.
0
votes
1answer
378 views

Connected and Unconnected Graph

Given a graph, G = (V,E), and conditions on members of V (that they must be connected to some m vertices, and disconnected to some n vertices), how can I efficiently find candidates for removal, based ...
1
vote
1answer
145 views

Spectrum of the adjacency matrix of strongly regular graphs

I am working through a proof of the following Theorem: Let $G$ be a connected, $k$-regular graph, $G\neq K_n$, then $G$ is strongly regular if and only if $|Spec(G)|=3$. Now I am having trouble with ...
1
vote
3answers
368 views

Show the union of two matching is bipartite

Let $G=(V,E)$ be a graph. Let $M1, M2$ be two matchings of $G$. Consider the new graph $G' = (V, M1 ∪ M2)$ (i.e. on the same vertex set, whose edges consist of all the edges that appear in either ...
1
vote
1answer
46 views

Balanced independent sets & independent domination number

Let $G=(V,E)$ be a bipartite graph, with partition $V=A \cup B$. Recall that an independent set $I$ of $G$ is a set of vertices sharing no edges. The independent domination number $i(G)$ is defined ...
4
votes
1answer
144 views

Determining the automorphism group of a disconnected graph

There is this know formula for determining the automorphism group of a graph $G$: let the connected components of $G$ consist of $n_1$ copies of $G_1$, $\dots$, $n_r$ copies of $G_r$, where $G_1, ...
0
votes
1answer
42 views

routing problem

I am wondering if there is any existing algorithm for the following routing problem. Let's suppose that you are given a directed graph where the edges are labeled with a weight indicating a cost. ...
4
votes
3answers
777 views

The complement of a graph G

I have a homework problem where I have a graph $G$ and I am tasked with proving that at least one of $G$ and $G$ complement is connected. However, I am unclear on the exact meaning of $G$ complement. ...
1
vote
0answers
278 views

How to show that union and intersection of min cuts in flow chart is also a min cut

The proof of this is everywhere skipped and said to be collorary of Ford-Fulkerson theorem. It's usually something like: Let $A$ and $B$ be low cuts of a flow chart. Then $A \cup B$ and $A \cap B$ ...
4
votes
1answer
104 views

Graph theory problem , acquaintances

Prove that in a group of 60 people one can always find two people with even number of common acquaintances. I just want a small hint to this problem , not a full solution .
0
votes
1answer
80 views

Hamiltonian Graphs and connected graphs

Prove or disprove: There exists an integer k such that every k-connected graph is hamiltonian.
1
vote
2answers
198 views

Induced subgraphs (graph theory)

I have the following graph theory question that I am stuck on: Prove or disprove: For every graph G and every integer $r \geq \text{max} \{\text{deg}v: v \in V(G) \}$ , there is an r-regular graph H ...
2
votes
1answer
170 views

Sort objects into groups based on group size preference

I have a research question that involves human subjects being sorted into groups before playing a social game. Before sorting, each person decides on their preferred group size, from 1 to n; where n ...
0
votes
1answer
46 views

Mathematical terminology of network measure

In advance I apologise for my lack of Mathematical knowledge and low quality question: I'm not trained as a mathematician, nor do I have a substantial knowledge of mathematical terminology. However, ...
0
votes
1answer
19 views

Intersection of minimal seperators

Let $S_1$ and $S_2$ be two minimal separators of a graph $G$ such that $S_1\cap S_2 \neq \phi$. Then is it true that $S_1 \cap S_2$ is also a minimal seperator.
1
vote
1answer
54 views

arbitrary graph has a n matching or an independent set having size at least |G|-2n+1

I am considering the problem: arbitrary graph has a n matching or an independent set having size at least |G|-2n+1. Could someone please show some ideas or outlines so that I can think about the ...
2
votes
1answer
43 views

Counting edges in a specially defined graph

$G$ has vertices $\{0, \ldots, pq - 1\}$, where $p, q$ are different primes. There is an edge between $x$ and $y$ if $p \mid x - y$ or $q \mid x - y$. How many edges does $G$ have? I looked at the ...
16
votes
5answers
3k views

What's the relation between topology and graph theory

I read the Wikipedia articles for both topology, graph theory (plus topological graph theory). Does topology encompass also graph theory? Or topology is only about studying shapes while graph theory ...
0
votes
3answers
750 views

If five teams are playing in a round robin tournament, is it possible for all five teams to tie for the first place?

If five teams are playing in a round robin tournament, is it possible for all five teams to tie for the first place? What if six teams are playing?
3
votes
0answers
40 views

Special graph theory

Is there a sub-field of graph theory that deals with weighted, directed graphs where two nodes are either connected in both directions, or neither? A simple real life application would be a hilly ...
0
votes
1answer
27 views

Find 2 graphs G and H…

I'm supposed to find two graphs $G$ and $H$ such that there exist morphisms $G\mapsto H$ and $H\mapsto G$, but $G$ and $H$ are not isomorphic. I just can't understand how that's even possible.. ...
2
votes
2answers
1k views

k-regular simple graph without 1-factor

Here's what I'm reading: every regular bipartite graph has a 1-factor. But I understand that not every regular graph has a 1-factor. So, I was thinking if it's possible to find a $k$-regular simple ...
3
votes
2answers
993 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
1
vote
2answers
87 views

Prove connectivity of graph with vertices of degree $\geq \lfloor \frac n2 \rfloor$ [duplicate]

Claim: A graph with vertices of degree at least $\lfloor \frac n2 \rfloor$ where $n = $ number of vertices and $n \geq 3$ is connected. I tried to prove this by contradiction, but I didn't know what ...
4
votes
1answer
1k views

A 3-regular graph with fewer than 3 bridges has a perfect matching

I've been trying to learn some graph theory on my own and I've come across this statement but no proof. It is apparently called Petersen's theorem but when I looked that up for a proof, it only proves ...
7
votes
0answers
373 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
2
votes
2answers
66 views

Which complete graphs are (edge) magic?

A magic labeling of a simple graph $G$ is a labeling of the edges of $G$ with distinct positive integers such that the sum of the labels of the edges incident to a vertex is the same for each vertex. ...
2
votes
1answer
148 views

spanning trees of an edge transitive graph

Let $G$ be an edge transitive graph. Let $t(G)$ be the number f spanning trees on $G$. Show that each edge lies in exactly $\tfrac{(n-1)t(G)}{m}$ spanning trees. Where $|V(G)|=n$ and $|E(G)=m$. ...
2
votes
0answers
146 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
1
vote
2answers
159 views

bridgeless graph

I need to prove that every graph containing only even vertices is bridgeless. I understand that an even vertex is one with an even degree. Therefore an even vertex is one which is connected to an ...
1
vote
1answer
146 views

Prove that flow is a linear combination of flow cycles and flow paths

Let $D=(N,A)$ be a directed graph, and for an arc $e=xy$ define $h(e)=x$ and $t(e)=y$. A flow is $\mathbf{x}=(x(e_1),\dots,x(e_k))$ with $\sum_{e:t(e)=v}x(e)=\sum_ {e:h(e)=v}x(e)$ for all $v\in ...
2
votes
0answers
136 views

Building Bayesian Networks, Causality and Cyclic Reasoning

I am studying Bayesian Statistics and I am trying to get a good understanding on Bayesian Networks, which seems to be vital in order to make something useful in Machine Learning. Most of the texts I ...
0
votes
1answer
86 views

Can a directed hamiltonian path be found in polynomial time?

I was discussing a programming competition problem with one of my math professors in Linear Algebra that reads as follows: A matrix is an $r\times c$ array of numbers, where $r$ is the number of ...
1
vote
0answers
46 views

What does it mean for two graphs to be consistent

I am trying to understand what does it really means for two graphs to be consistent in the context of bidirectional transformation ? Can you provide me with a good example? Thank you in advance.
0
votes
1answer
166 views

Eulerian paths in non-traversable graphs

Suppose I have a weighted connected graph which is traversable (each vertex has even degree) and I wish to walk over all edges. Clearly any Eulerian path minimizes the total weight. What can be said ...
1
vote
1answer
78 views

Question about trees

When must an edge for a connected simple graph appear in every spanning tree for this graph? I would have thought it was the midpoint of the longest simple path in the graph. However, there would ...