Tagged Questions

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
1answer
10 views

Can the complete graph K9, be 2-coloured with no blue K4 or Red triangles? (Ramsey Theory)

I am working on the following problem on 2-coloured complete graphs: '$K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and blue ...
1
vote
1answer
7 views

Prove that you cant you fill all spots in this grid.

We have a $4$ by $5$ grid with $A$ in the lower left corner, and $B$ in the middle of the left lane. Why can't you draw a line from $A$ to $B$ which goes through all the spots in the grid? This ...
1
vote
0answers
18 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
-1
votes
0answers
19 views

Neutron-Density cross-plot interpretation

I have a question about solving a particular graphical problem. This is a picture of a Neutron-Density cross-plot: It's a little bit confusing as plots go, so allow me to try to explain the salient ...
0
votes
1answer
21 views

Finding nodes with a particular weight in a graph

Say that an edge $e$ is incident to a node $v$ if one of its two extremes is $v$. Then we can also say that $v$ is hit by $e$. We might define the notion of "weight of a node $v$" as the sum of all ...
0
votes
1answer
6 views

Calculate edge probability of a graph

I wonder what is the edge probability $p$ for which a random graph with $n = 5000$ nodes has the largest expected diameter? How can I calculate that? Is there someone who can help me? This would be ...
0
votes
0answers
13 views

A small confusion in network flows (conservation constraints).

I'm reading the Handbook of Graph Theory. I guess It says that the sum of the flows going is equal do the sum of flows going back, I'm confused about what is the value of the flow going ...
1
vote
2answers
15 views

Proof of connectedness in a simple graph

Let G be a simple graph with n vertices. Prove that if the degree of every vertex is at least $\frac{n-1}2$, then G is connected. I've tried the degree sum formula, but it doesn't seem to get me ...
0
votes
1answer
15 views

Probability of edges in Graph

I have given a random graph G(n, p) with n = 5000 vertices and an edge probability of p = 0.004. I calculated the expected number of edges which is (0.004 * maximum number of possible edges) $pE = ...
0
votes
0answers
25 views

why Petersen graph has exactly six perfect matching? [on hold]

Must I find all six matching and show, that there cannot be more? I know, that all cubic graphs have at least 5 matching.
0
votes
1answer
25 views

Fundamental group of graphs

If $G$ is a connected graph with a maximal tree $T \subset G$ such that: $G-T$ consists of only a single edge $e$, then how would i find the fundamental group $\pi_1(G)$ and show that it ...
0
votes
0answers
29 views

How many first neighbors does a node whose degree is known in an undirected graph have?

Consider a graph $\mathcal{G} = \left(V,E\right)$ with vertices (nodes) $V$ and undirected connections between them $E$. If I know the degree of the $i$th node, $d\left(i\right) = k$, and the ...
1
vote
0answers
33 views

Example of a series parallel graph with toughness greater than $\frac{4}{7}$

Can anyone lead me to an example of a "more than $\frac{4}{7}$ tough series parallel graph"? Graph toughness is defined as $T = \min \left\{\frac{|a|}{\omega{(G\backslash A)}}\right\}$ over all ...
0
votes
1answer
17 views

quotient graph $G^R$

I understand that if $R$ is an equivalence relation on $G$, the resulting partition cells are either equal or disjoint. I think I understand that the graph of the quotient set $G^R$ is constructed ...
0
votes
1answer
40 views

What is $\Gamma(a)$?

I'm reading Van Lint's Course in Combinatorics: He mentions $\Gamma(a)$ in this text but I'm not really sure of what it means and I'm also afraid of assume something wrong, at first thought I ...
0
votes
0answers
25 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
33 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
40 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
22 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
34 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
21 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
0answers
23 views

deleting edges in bipartite graph

Show that deleting at most $(m−s)(n−t)\over s$ edges from a $K_{m, n}$ will never destroy all its $K_{s, t}$ subgraphs. Any hints or proofs are greatly appreciated. I was thinking about using ...
1
vote
1answer
19 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
22 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
57 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
vote
0answers
29 views

average degree inequality

Let $G$ be a graph with $|E(G)| ≥ 1$ and average degree $d(G)$. Prove that $G$ contains a subgraph $H$ with $δ(H) >{d(H)\over 2} ≥{d(G)\over 2}$. I'm not sure how to show that $δ(H) >{d(H)\over ...
-1
votes
0answers
12 views

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

Need help with this one if L(G) is a complete graph then F is a star - True or false
1
vote
1answer
29 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
22 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
28 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
0answers
24 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? [on hold]

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
13 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 ...
0
votes
0answers
32 views

Extremal Proofs

Let $k ≥ 1$ be an integer, and let $G$ be a connected graph on $n$ vertices. Prove that $(a)$ $G$ contains a path of length $k$ if $n ≥ k+ 1$ and $d_G(u)+d_G(v) ≥ k$ for any two non-adjacent vertices ...
3
votes
0answers
37 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
0answers
14 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
17 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
29 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: ...