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

0
votes
0answers
28 views

What's the meaning of dual concept?

I've read the following on The Handbook of Graph Theory: 11.1.2 Minimum cuts and Duality An important and dual concept related to maximum flows is that of minimum cuts. I know that the value ...
0
votes
1answer
38 views

Proving a connected graph cannot have only even-degree vertices

I want to prove that a connected graph with m edges and n vertices must have at least one vertex of odd degree. In particular, I want to prove this for a graph of 53 edges and 11 vertices; but also in ...
0
votes
0answers
41 views

Finding spanning trees using Depth-First Search

I am wondering if root in spanning trees using Depth-First Search can have more than $2$ children? I know this is a silly question, but there is an example in the book which involves only $2$ ...
-1
votes
0answers
24 views

Is it true that a tree on n vertices has n-1 edges and graph has 2n edges? [on hold]

I'm a bit confused how can these two theorems exist at the same time. A tree on n vertices has n-1 edges but graph has 2n edges [Hand-Shaking Lemma]. I know Induction Proof for the first part but the ...
0
votes
1answer
35 views

Prove that every connected undirected graph with n vertices has at least n-1 edges.

I would appreciate it if anyone can verify my proof. It is a proof by induction, but I attempt to reason things out rather than using a purely mathematical approach, in a similar vein to many other ...
1
vote
0answers
23 views

Random walk return for subgraph

Assume that $G$ is a finite graph and we have a simple random walk starting at some vertex $v$ of $G$. We fix $n$, and consider the probability that the random walk does not return to $v$ after $n$ ...
1
vote
1answer
20 views

Connectivity of a Hamiltonian path

Show that if G has a Hamiltonian path then for every proper subset S of V, $\,$ $\omega(G-S)\leq\vert S \vert + 1$,$\,$where V is the set of the vertices of G and $\omega$ is the number of the ...
0
votes
0answers
23 views

Evaluation a function of degree of vertices in a graph

I have a function $f(d)$ which takes in the degree of a vertex of a node in a graph $G$ and outputs a number between 0 and 1. The function is specified as follows. ...
0
votes
0answers
16 views

orbits/canonical labelling of colored graphs

Consider the following setting. We are given a simple undirected graph $G$ and a coloring $c:V(G) \mapsto \{0,1\}.$ We can compute the canonical labelling and $\rm{Aut}(G)$ efficiently. What I ...
1
vote
0answers
15 views

Combinatorial designs give triangulations of complete graphs

I recently attended a talk on combinatorial design theory. The speaker mentioned briefly that the Fano plane, and other designs give rise to triangulations of complete graphs (the Fano plane gives a ...
1
vote
1answer
60 views

Largest number of edges removed from $Q_{10}$ such that the graph always has a Hamiltonian cycle.

What is the largest number of edges that can be removed from $Q_{10}$ such that the graph always has a Hamiltonian cycle. Obviously it is $\leq 8$ as otherwise you can take $9$ edges away from one ...
0
votes
1answer
17 views

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself).

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself). I don't think this is possible, I have done a fair bit ...
-1
votes
0answers
12 views

if L(G) is a complete graph then F is a star - True or false [closed]

Need help with this one if L(G) is a complete graph then F is a star - True or false
1
vote
1answer
32 views

3-connected graphs simple question

I have a relatively simple question. I was given this exercise A graph $G$ is called $2$–connected if for every pair of vertices $x$ and $y$ there are at least $3$ internally disjoint $xy$–paths in ...
0
votes
0answers
16 views

Special partitions for cubic 3-edge connected graphs

I'm trying to prove the following A cubic 3-edge connected graph $G = (V, E)$ allows partitions $T_{i}\subset E$ such that $G\setminus T_{i}$ is 2-edge connected, for $i = 1,\ldots, 5$. In ...
0
votes
2answers
26 views

Property of the numbering in preorder traversal of the tree

$v$ denotes the vertex which has been asigned the number $v$. The vertices are numbered in the order visited. In preorder all vertices in a subtree with root $r$ have numbers no less than $r$. More ...
0
votes
1answer
27 views

A cycle in an undirected graph

A cycle is a simple path of length at least $1$ which begins and ends at the same vertex. In an undirected graph, a cycle must be of length at least $3$. Could you explain me why that stands??
0
votes
0answers
29 views

Algorithm Generate all labeled graphs

I'm trying to find an algorithm which will generate all labeled graphs with $n$ nodes and $n-1$ edges. It must cover trees and graphs with cycles with one unconnected node, but without multigraphs. ...
0
votes
1answer
33 views

Maximum flow problem with both minimum and maximum capacities

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum ...
1
vote
2answers
47 views

Simple proof by contradiction in graph theory

The question is as follows: Let P be the longest path in a simple graph G, and let $\lambda$ be the length of P. Show that both the starting point and ending point of P must have degree $\le\lambda$. ...
0
votes
0answers
30 views

Proof that no Eulerian Tour exists for graph with even number of vertices and odd number of edges

How would you prove that for a connected graph with an even number of vertices and an odd number of edges, at least one of the vertices has an odd degree? My first attempt at solving this has been to ...
0
votes
0answers
10 views

What is a scale free network? [closed]

What I want to know is what scale is a 'scale-free network' free of? This is a the part I'm confused on.
0
votes
4answers
18 views

Infinite set of graphs neither of which are homeomorphic

Show that there is an infinite set of graphs $\{G_1,G_2,...\}$, where: $\quad \quad \quad$ $\forall i, \forall j, i\neq j :$ graph $G_i$ isn't homeomorphic to graph $G_j$ I have a hard ...
0
votes
0answers
14 views

All-pairs shortest paths - undirected graph with non-negative integer weights

I was trying to find the current fastest algorithm for all-pairs shortest paths (APSP) on an un-directed graph with non-negative integer weights. I could not find anything better than Shoshan and ...
1
vote
1answer
34 views

Show that if either (a) G is not 2-connected, or , (b) G is bipartite with bipartition (X, Y) where IXI different to lYI, then" G is non hamiltonian.

This is a question I found in the Graph Theory book by Bondy and Murty (4.2.1). I do not know Graph theory (I am a biologist) but I am starting to use some results in my line of work and I really need ...
-4
votes
0answers
17 views

Show that in a simple graph G if δ ≥ (n-1)/2 then λ = δ [closed]

Where n is the number of vertices of graph G, δ is the minimum degree and λ is the edge connectivity
0
votes
0answers
8 views

Let G be a k-edge-connected graph and X be a k-edge-cut of G show G/X and G/X complement are k-edge-connected

I basically just know the definitions of edge connectivity and contraction of a graph, I don't know any theorems on the topic yet, but I am allowed to use any theorem or lemma whatsover so long as I'm ...
3
votes
0answers
38 views

How many ways to place 3 non-attacking bishops given the following conditions

How many ways are they to place 3 non-attacking bishops on an $n \times n$ board such that $2$ of these bishops are placed within the $(n-1) \times (n-1)$ board and the other 1 is placed outside of ...
0
votes
1answer
17 views

Point location( planar subdivision)

Show that, given a planar subdivision S with n vertices and edges and a query point q, the face of S containing q can be computed in time O(n). Assume that S is given in a doubly-connected edge list
0
votes
2answers
25 views

Directed acyclic graph problem

Love some guidance on this problem: G is a directed acyclic graph. You want to move from vertex c to vertex z. Some edges reduce your profit and some increase your profit. How do you get from c to z ...
0
votes
1answer
18 views

Let G and H be simple graphs. Show $k$(GvH)= min {$v$(G)+$k$(H),$v$(H)+$k$(G)}

where $k$ is connectivity and v is the join operation. This problem's got me really confused, I can't find any relation between the connectivity and the amount of vertices
0
votes
0answers
30 views

Find a strong orientation such that $G$ can reach $D$ within $7$ steps.

Find a strong orientation such that $G$ can reach $D$ within $7$ steps. I found the following strong orientation. Can it be counted as an answer since I can reach from G to D in 1 step? EDIT: ...
0
votes
0answers
14 views

Findind diameter of minimum spanning tree in matlab

hello I am trying to find the diameter of a spanning tree using Matlab's function graphshortestpath().I have a 23 indices spanning tree and I want to find it's diameter. I use these parameters in a ...
1
vote
1answer
39 views

Simple Tree Proof

I am taking an introductory proofs course and I find it difficult to formulate a proof even though it may be something trivial. In essence I find it difficult to determine whether I should use a ...
1
vote
0answers
15 views

trail vs path in Graph Theory v/s Graphical Models

In my course on probabilistic graphical models, I learnt (quoting from page 36 of the book Probabilistic Graphical Models: Principles and Techniques by the same author) Path: We say that X1 , . . . ...
1
vote
1answer
46 views

Coloring of regular graph's edges

There is a regular graph. Degree of each vertex is four. It needs to prove that edges of the graph can be colored in two colors so that each vertex is incident to two edges of the same color and the ...
0
votes
1answer
35 views

Graph proof question

Let G be an undirected graph. Suppose you start at a vertex v and walk along the edges of G obeying the following two rules. (I) You may not use the same edge twice travelling in the same direction ...
0
votes
0answers
19 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
0
votes
0answers
12 views

Prove: if G has exactly one $C$-fragment, then there exists a cycle $C$ in a 3-connected graph that is the boundary of a face in $G$.

If G has exactly one $C$-fragment, then there exists a cycle $C$ in a 3-connected graph that is the boundary of a face in $G$. If there is a cycle, then it has to be the boundary of a face (right?). ...
2
votes
1answer
95 views

Fight against the Hydra - Graph Theory

The following problem is supposed to be a nice application of the basic knowledge of graph theory. I consider it however as difficult and I would be happy if someone could help me find a solution. ...
1
vote
2answers
27 views

Edge contraction and subdivision

Let $G$ be a $3$-connected graph that is not homeomorphic to $K_5$ or $K_{3, 3}$. Let $G'$ be the graph obtained from $G$ by contracting an edge. Why is it the case that $G'$ contains no ...
0
votes
0answers
14 views

Why does adding a vertex $x$ that is adjacent every vertex in $G$ with a subdivision in $K_{3,3}$ or $K_5$ result in subdivison of $K_5$ or $K_{3,3}$

Why does adding a vertex $x$ that is adjacent every vertex in a subdivision in $K_{2,3}$ or $K_4$ result in a graph that is a subdivision of $K_5$ or $K_{3,3}$?
0
votes
1answer
60 views
+50

Chromatic number proof verification

Prove that $χ(G) ≤ 1 + \text{max}\{\text{deg}_{G} (x): x ∈ V\}$ holds for every (finite) graph $G = (V, E)$. Let's consider the worst case for graph colouring. To obtain the maximal case, we connect ...
2
votes
2answers
57 views

A tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)

Let T be a tree tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)
0
votes
0answers
14 views

How to find all possible minimum cut in a directed graph?

The problem I have asks me to identify each node in the flow graph to be either: nodes that lie on the sink side of every minimum cut. nodes that lie on the source side of every minimum cut. nodes ...
0
votes
0answers
22 views

How many edges must you remove from Peterson graph to make it planar

The answer is 2. Why is it not 1? Context: I understand that the Peterson graph is not planar (b/c it contains $K_{3,3}$). What I don't understand is why 1 removing 1 edge doesn't do the job. I've ...
1
vote
1answer
21 views

Clarification on notation

For a graph $G$, put $δ(G) = \text{min}\{\deg_{G} (v) : v \in V\}$ (the minimum degree of $G$). Prove $χ(G) \leq 1 + \text{max}\{δ(G ) : G' \subseteq G\}$, where $G' \subseteq G$ means that $G$ is a ...
0
votes
2answers
23 views

Partitioning graph edges into two cycleless sets

Given a directed graph $G=\left(V,E\right)$, provide an algorithm that partitions $E$ into two disjoints sets $E_1,E_2$ such that $E=E_1\cup E_2$ and $G(V,E_1)$, $G(V,E_2)$ have no cycles. The ...
0
votes
2answers
23 views

Determine whether the networks below are isomorphic

Determine whether the networks below are isomorphic They meet the requirements of both having the same number of vertices. They have the same number of edges They both have 8 vertices of degree ...
0
votes
0answers
39 views
+50

Prove or disprove:If 2 flows in $N$ that agree on $[X,\overline X]$ and $[\overline X, X]$then $f_1$ and $f_2$ are maximum flow in $N$

Let $N$ be a network with capacity function c and suppose that $[X,\overline X]$ is the minimum cut in $N$. Prove or disprove: a) If $f_1$ and $f_2$ are flows in $N$ that agree on arcs( every arc in ...