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

2
votes
4answers
4k views

Is a graph simple, given the number of vertices and the degree sequence?

Does there exist a simple graph with five vertices of the following degrees? (a) 3,3,3,3,2 I know that the answer is no, however I do not know how to explain this. (b) 1,2,3,4,3 No, as the sum of ...
3
votes
1answer
310 views

network flow as a linear combination

How would I write the flow of the following graph as a linear combination of flows along s,t-paths and t,s-paths and cycles? The values of the edges in the graph represent the flow along that edge. ...
4
votes
3answers
1k views

Proving that a graph of a certain size is Hamiltonian

For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian. I know that if I can show that the degree sum of any ...
3
votes
1answer
168 views

How many different four coloring exist for a given regular map?

Excluding maps that can be colored with 2 or 3 colors, how many different four coloring exist for a given regular map? Naturally, two identical maps have to be regarded as differently colored if the ...
1
vote
1answer
273 views

How many directed graphs with N nodes contain a given directed cycle of length L?

Given a directed graph $C$ that only contains a directed cycle of length $L$ (and all resulting sub-cycles), that visits each node at least once, $$C=(V, D)$$ where $V$ is a fixed set of vertices ...
-1
votes
1answer
214 views

Uniform Cost Search on Graph Proof

I am trying to prove the following: For any positive natural n, there exists an undirected graph of n nodes, positive natural edge widths, and nodes s and t such that a uniform-cost search from s ...
5
votes
1answer
1k views

Dijkstra's algorithm using heap

My teacher gave me a pseudocode of Dijkstra's algorithm using binary heap including the following steps (x was just extracted from the heap): For each vertex y such that it is a node for it in a ...
3
votes
2answers
238 views

isomorphic graphs adjacency lists

Is there an algorithm which will allow me to find an isomorphism between two graphs if I have their adjacency lists?
0
votes
0answers
227 views

Cycle Basis = Matroids? How is it even possible?

Can anyone explain to me why a cycle basis hones the properties of a matroid? Especially points 2 & 3. How can a subset of I also be a member of I? Isn't a cycle basis supposed to be consisted of ...
11
votes
3answers
1k views

Homology and Graph Theory

What is the relationship between homology and graph theory? Can we form simplicial complexes from a graph $G$ and compute their homology groups? Are there any practical results in looking at the ...
1
vote
1answer
198 views

Rank of a graph matrix

$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$. There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
3
votes
0answers
224 views

Checking the biconnectivity of a biconnected graph with a vertex removed

If I have a biconnected graph and I remove a vertex (without forgetting which vertex was removed and which vertices it was adjacent to), is there an way to check the biconnectivity of the resulting ...
4
votes
1answer
258 views

Perron-Frobenius Theorem and Graph Laplacians

How can the Perron-Frobenius theorem be used to show that for a connected graph, there is a simple eigenvector that is (i) real and (ii) smallest in magnitude and (iii) has an associated eigenvector ...
17
votes
4answers
5k views

Logic question: Ant walking a cube

There is a cube and an ant is performing a random walk on the edges where it can select any of the 3 adjoining vertices with equal probability. What is the expected number of steps it needs till it ...
3
votes
2answers
498 views

Union on Graph Data in Mathematica

I have begun working with Mathematica for some Graph Theory, and I want to compute the number of spanning trees of all cubic graphs up to 12 vertices. I have found that GraphData["Cubic", 12] will ...
3
votes
2answers
253 views

Cycles of Specified Length in a Graph

Let $G=(V,E)$ be a graph, and $A$ be its adjacency matrix. Define $n = |V|$. Given $A$ and a natural number $m \le n$, I'm interested in the following problem: How many simple cycles of length ...
16
votes
8answers
4k views

What are good books to learn graph theory?

What are some of the best books on graph theory, particularly directed towards an upper division undergraduate student who has taken most the standard undergraduate courses? I'm learning graph theory ...
1
vote
1answer
560 views

Floyd's algorithm for the shortest paths…challenging

If anyone has some insight on how to do this it would be very much appreciated.
7
votes
7answers
701 views

How many countable graphs are there?

Even though there are uncountably many subsets of $\mathbb{N}$ there are only countably many isomorphism classes of countably infinite - or countable, for short - models of the empty theory (with no ...
3
votes
2answers
284 views

Asymptotic number of unlabeled graphs

A rather tight lower bound $c(n)$ of the number of unlabeled digraphs of order $n$ (loops allowed) seems to be $$c(n) = 2^{n^2}/n!$$ because there are $2^{n^2}$ labeled graphs, almost all of them ...
8
votes
1answer
267 views

Software for drawing and analyzing a graph?

I would like to know a good program for drawing graphs and analyzing them (finding Eulerian circuits, Hamilton cycles, etc.). I would also like to export the drawing to Word.
5
votes
2answers
121 views

Euler graph having simple cycles

One property of Euler graphs is that if a graph with $n \geq 3$ vertices and more than $n$ edges has an Euler circuit, then it has more than two simple cycles. How can we prove it?
4
votes
2answers
603 views

If given the girth and the minimum degree of a simple graph $G$, can we give a lower bound on the number of vertices it has?

I'm trying to prove that every simple graph $G$ of girth $g(G)=5$ (length of smallest cycle), and minimum degree $\delta$, has at least $\delta^2 + 1$ vertices. I tried using induction on $\delta$ ...
0
votes
1answer
574 views

Bipartite graph partitioning

I have a bipartite graph and I want to partition each of the two sets of nodes (I don't know the technical term for these sets I mean each part of the bipartite graph) separately. Each node hase a ...
2
votes
1answer
252 views

Graph - MST in O(v+e)

G=(v,e) , with weight on the edges than can be only a or b (when $a I need to find MST of the graph in O(v+e). I think to put all the edges in array, and than scanning the array. first only check ...
-3
votes
1answer
101 views

Labeled and unlabeled categories

When one talks about the category $V_K$ of vector spaces over a field $K$ and considers the dual functor $D$ which maps a vector space $V$ to its dual $V^{*}$ I believe to have in mind something like ...
1
vote
2answers
459 views

Graph - Minimum spanning tree

I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$). Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum ...
6
votes
3answers
922 views

What are the most important results in graph theory?

What are the theorems/results/widely applicable results in graph theory that everyone should know about?
1
vote
0answers
258 views

Partition of graph into independent sets of consecutive vertices

Sorry for my English. Here is the question: $G=(v,e)$, undirected graph, $V=\{v_1,v_2,\ldots,v_n\}$. the vertices are organized in sequence from the smaller one to the biggest $v_1,\ldots,v_n$. We ...
6
votes
1answer
613 views

Perfect Matching in a bipartite graph with a constrained degree sequence

Given a bipartite graph G with two partition sets $U$ and $V$ of the same size $n$. In each set, there are d vertices of degree (n-d+1), and n-d vertices of degree (n-d). Can we find a perfect ...
1
vote
1answer
726 views

Chromatic number and non-simple cycles

Is there any theorem that apllies to non simple cycles and chromatic number? For example we know that x(G)=2 if G does not contains odd cycles. What about a non-simple cycle that contains odd ...
3
votes
2answers
1k views

How do I write this proof more formally?

So the question asks, given that we have a undirected graph with unique edge weights, prove that the graph has a unique minimum spanning tree. My Proof: If the graph has unique edge weights, we can ...
1
vote
1answer
258 views

Graph Problems(Euler,Hamilton,Color)

Let be $n_1$, $n_2$ such natural numbers that $n_1\geq 3$ and $n_2\geq 3$ and let be $G_{n1,n2}$ a graph that takes shape by taking $G_{n_1}$, the cycle of $n_1$ vertices, and $G_{n_2}$ the cycle of ...
2
votes
2answers
86 views

Forcing bipartite graphs?

Show that deleting at most (m-s)(n-t)/s edges from a K_{m,n} will never destroy all its K_{s,t} subgraphs. I'm completly stuck here and any help would be welcome!
1
vote
1answer
107 views

Graph - reduction

Sorry for my English. Here is the question: Graph (V,E). Definition: Legal's up-path in a graph from s to t is existent if and only if for every Vi, Vi+1 (for each i) fulfill w(Vi)<=w(Vi+1), ...
4
votes
1answer
239 views

Getting generators of graphs automorphism group

Suppose I have a graph like this and a list of its automorphisms. How do I go about getting a set of generators for this group?
2
votes
1answer
647 views

Why is the Fundamental Group of a Connected Graph $G$ Free on elements in $G-T$; $T$ spanning tree for $G$)

The fundamental group $\Pi_1(G)$ of a connected graph $G$ is defined to consist of all loops (i.e., closed paths) based at a given fixed basepoint/vertex $g \in G$ as elements, and concatenation ...
2
votes
2answers
791 views

Showing that a graph has a cycle length less than something

I have the following exercise to do but don't know how to approach it: Let $G$ be a graph with $n$ nodes ($n \ge 2$), and where every node has degree at least $3$. Show that $G$ has a cycle of length ...
1
vote
1answer
102 views

Indicate reverse of graph transition

I have the following (directed) graph: A --> B the transition is labled C. Is there symbol to denote the inverse of the (A,B) transtion?
3
votes
2answers
327 views

Graph coloring problem (possibly related to partitions)

Given an undirected graph I'd like to color each node either black or red such that at most half of every node's neighbors have the same color as the node itself. As a first step, I'd like to show ...
8
votes
0answers
147 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant ...
2
votes
1answer
121 views

Graph enumeration problems which admit recursive solutions

This is an attempt to refine my previous question into something precise enough to admit a resolution. Let $P\;$ be a graph property, let $T_n\left(P\;\right)$ be the set of isomorphism classes of ...
2
votes
0answers
70 views

Comparing symbolic and analog descriptions

I've never seen the following comparison before. Let me start with a specific example: Given a finite structure with two symmetric binary relations, i.e. a graph $G$ with one vertex set $V$ and two ...
15
votes
1answer
755 views

Did the Appel/Haken graph colouring (four colour map) proof really not contribute to understanding?

I hope this isn't off topic - sorry if I'm wrong. In 1976, Kenneth Appel and Wolfgang Haken proved the claim (conjecture) that a map can always be coloured with four colours, with no adjacent regions ...
1
vote
1answer
61 views

Covering and Cycles

Let $G = (V, E)$ and $G' = (V', E')$ be two graphs, and let $f: V \rightarrow V'$ be a surjection. Then $f$ is a covering map from $G$ to $G'$ if for each $v \in G$, the ...
16
votes
2answers
775 views

Not lifting your pen on the $n\times n$ grid

The question I am asking has basically already been asked. Please see this MSE thread. There are a few questions brought up on that thread, and a smaller number were answered. The reason I am ...
6
votes
1answer
2k views

Number of simple paths between two vertices on an $n \times m$ square-grid graph?

I've encountered this whilst writing an optimisation benchmark for some heuristic search algorithms. Feels like there should be a basic solution out there! A square-grid graph is constructed from $n ...
0
votes
1answer
153 views

Numbers defined on graph structures

I asked a question yesterday regarding numbers defined on graph structures that I call graph numbers. I posted the algorithm I was using to define graph numbers, which are simply a natural extension ...
2
votes
2answers
443 views

Number of inner nodes in relation to the leaf number N

I am aware that if there is a bifurcating tree with N leaves, then there are (N-1) internal nodes (branching points) with a single root node. How is this relationship proved? Best,
4
votes
3answers
302 views

Higher dimensional analog to planar graphs?

We usually say that a graph is planar if it can be embedded into 2-space s.t. no edges intersect. Here's a different way to describe the same situation: a graph is planar if it can be embedded into ...