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
12 views

Maximum flow between three edges in a flow network

I am assuming that the following fact is true in a flow network N(G(V,E) ,s,t,c ) Let us say A,B,C belongs to E in a finite directed graph G. F(x,y) is maximum flow in the network N, then the ...
0
votes
1answer
13 views

Transition matrix to graph

Is there a program which can given a transition matrix $P$ draw a graph from a it? The transition matrix is also known as stochastic matrix and probability matrix see ...
1
vote
0answers
13 views

Prove that if $deg (v) \geq \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian.

Let $G$ be a bipartite graph with partite sets $U$ and $W$ such that $|U|=|W|=k \geq 2$. Prove that if $deg (v) > \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian. Dirac's theorem : ...
1
vote
0answers
16 views

Find a neccessary and sufficient condition for $G$ to be Hamiltonian

a) prove that $K_{r,2r,3r}$ is Hamiltonian for every postive integer $r$ b) prove that $K_{r,2r,3r+1}$ is Hamiltonian for no postive integer $r$ c) Let $G=K_{n_1 , n_2, \dots ,n_k}$ be the complete ...
2
votes
0answers
29 views

Dividing tournament into “equal” groups

In a tournament of $n$ teams, each team plays all other teams exactly once, with no draw. For which $n$ is it always possible to divide all teams into several groups so that each group of teams won ...
1
vote
1answer
27 views

A simple problem of graph theory.

There are how many $4$ vertices connected graphs not including a triangle? My try:I made 3 such graphs.Is it maximum possible number of such graphs or there are many others?Is there any formula in ...
1
vote
0answers
15 views

Show that $G$ is $2$-connected but not necessarily Hamiltonian

Let $G$ be a graph of order $n\geq 3$ having property that for every vertex $v$ of $G$, there is a Hamiltonian path with initial vertex $v$. Show that $G$ is $2$-connected but not necessarily ...
0
votes
0answers
6 views

Find mimimum hamiltonian path with a “Magic” SP algorithm

I want to find a minimum Hamiltonian path in a graph $G=(V,E)$ with edge cost $c:E\rightarrow \mathbb{R}^+$ from $s$ to $t$ with $s,t \in V$. Suppose we have a Magic algorithm that yields a shortest ...
1
vote
1answer
21 views

Prove that if $G$ and $H$ is Hamiltonian then $G \times H$ is Hamiltonian

Prove that if $G$ and $H$ is Hamiltonian then the Cartesian product $G \times H$ is Hamiltonian Theorem 3.16: If $G$ is Hamiltonian and $S$ is the vertex cut then $$k(G-S) \leq |S|$$ This ...
0
votes
1answer
17 views

How many 1-regular graphs can be produced by deleting edges from a even complete graph?

Given a complete graph $K_n$ where $n > 1$ and $n$ is even, how many distinct 1-regular graphs can be produced by only deleting edges? By "distinct" I mean the vertices are numbered or taken based ...
2
votes
1answer
33 views

A table with m rows and n columns [on hold]

A table with $m$ rows and $n$ columns is filled with nonnegative integers such that each row and each column contains at least one positive integer. Moreover, if a row and a column intersect in a ...
0
votes
0answers
11 views

Increasing the speed of a depth first search.

I am looking for ways to increase the speed of a depth first on a graph when trying to find a path from a source node to a destination node. One thing I have tried is to perform a bidirectional ...
1
vote
2answers
17 views

Help with proof of the existance of a graph produced from deleting edges

Prove that every connected graph with an even number of vertices can be transformed into a graph with uniform degree 1 by only deleting edges. I have tested this with pen-and-paper and it seems to be ...
1
vote
0answers
9 views

possible embeddings for a $2$-connected planar graph

When I asked the question "cycles and faces in planar graphs", I learned that the numbers of vertices in the faces are not unique, if the planar graph is only $2$-connected. My question now is : How ...
1
vote
0answers
11 views

Examples of sequences of graphs with different order of Cheeger constant and spectral gap

According to Cheeger's inequality, the bottleneck ratio/Cheeger ratio $\Phi_*$ of a graph and the spectral gap $\lambda$ of its adjacency matrix satisfies $$\Phi_*^2/2 \leq \lambda \leq 2\Phi_*. $$ ...
1
vote
2answers
14 views

How can I prove that a graph with a required amount of edges per node is invalid?

For the following example I assume that no node may be connected to itself. Nodes: A, B, C, ...
0
votes
1answer
24 views

Proving two graphs are isomorphic in polynomial time - Bondy/Murty - Graph Theory Page 6

I am trying to do the below problem: Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since it is $3\text{-regular}$. I ...
0
votes
0answers
27 views

Does $\beta(G)=\alpha'(G)$ always?

Does there exist a graph where the minimum vertex cover does not equal the size of the maximum matching? I'm thinking that if it does, then it cannot be a bipartite graph and so it contains an odd ...
0
votes
0answers
11 views

Markov chains: identifying a nonregular transitional matrix

I am currently TA'ing for a course in which the students are soon to learn about Markov chains and stochastic matrices. During the sections, it refers to the possible existence of a stable state and ...
-1
votes
1answer
12 views

Graph theory problems about vertices and interior angles.

I have three problems of graph theory: $1.$We have a $10$ gon then maximum number of acute angles that we can make is? $2.$We have $5$ vertices then how many connected trees we can make? $3.$How ...
-2
votes
0answers
20 views

Number of triangles in a graph and its complement

Let $G$ be a simple graph with $|V(G)|=n$ and $|E(G)|=e$. let $T$ be the number of triangles in $G$. Show that $T ≥\frac{4e}{3n}(e-\frac{n^2}4)$ and find a larger possible lower bound for ...
0
votes
2answers
22 views

A simple problem of graph theory about the degree of vertices.

A graph has $7$ vertices and $10$ edges then which is true? $(I).3$ vertices of degree $4$ and $4$ vertices of degree $2$. $(II).2$ vertices of degree $5$ and $5$ vertices degree $2$. $(III).$Every ...
0
votes
1answer
19 views

$3$-connected non-hamiltonian graph with at most $3$ independent vertices

Is there a $3$-connected non-hamiltonian graph with at most $3$ independent vertices ? I checked the graphs upto $9$ vertices and the cubic graphs upto $18$ vertices and did not find such a graph. ...
3
votes
1answer
23 views

Find maximum number of nodes in a regular graph of degree 4 and diameter 2

In $n$ nodes directed graph, every vertex has in-degree and out-degree equal to $4$. If every vertex is reachable from every other vertex directed by a path of length at most $2$. How can we find ...
1
vote
0answers
18 views

Mapping graphs to themselves, e.g. the meta-graph

I'm looking for any prior work on a (for lack of a better word) meta-graph. Let $M=(V,E)$ be a a meta-graph with vertex and edge set $V,E$. The meta-graph is formed by mapping a set of graphs $G = ...
0
votes
1answer
19 views

The complexity of Depth First Search

Can anyone tell me what's the complexity of Depth First Search? I have no idea about what does mean by the complexity.
0
votes
4answers
53 views

Prove that $G$ has at least $q-p+c$ cycles.

I need your help with this question: Suppose that a graph $G$ has $p$ vertices, $q$ edges, and $c$ components. Prove that $G$ has at least $q-p+c$ cycles. I don't know how to prove that.
0
votes
0answers
17 views

Breaking Ties Alphabetically Using Kruskal's Algorithm

Kruskal's Algorithm picks the next edge simply by picking the lightest edge. Doesn't that make breaking ties alphabetically impossible? If I had a graph where two edges ...
1
vote
2answers
54 views

Proving that every connected graph has a vertex whose removal will not disconnect the graph.

I have not done much proofs before this and need some guidance. I know that for a simple graph such as this : node - node - node -node Removing the first and ...
1
vote
0answers
9 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
2
votes
1answer
54 views

Are “almost all” graphs hamiltonian?

Let $$p(n):=\frac{\text{number of hamiltonian graphs with $n$ nodes}}{\text{number of graphs with $n$ nodes}}$$ Since $883156024$ of the $1018997864$ graphs with $11$ nodes are hamiltonian, we have ...
0
votes
1answer
21 views

decomposition of graph to cycle and cut space

Let $G$ be a graph. I want to show that $E(G)$ is disjoint union $C\cup D$ where $C$ and $D$ belong to cycle and cut space respectively.
0
votes
1answer
11 views

Extremal graph theory

Determine ex(n,2K2) for every n. (2K2 means a pair of vertex-disjoint edges, ex(n,H) = max{e(G): |G| = n is H-free}) I think the answer might be n+1 choose 2 but I am stuck on where to start.
0
votes
1answer
14 views

Graph Theory (Vertex Connectivity)

Show that for any edge $e\in E(G)$, $κ(G−e)\geκ(G)−1$. ($e$ is an element of the edge set, $κ(G)$ is vertex connectivity) I think this follows from Mengers theorem, but I am having trouble seeing ...
5
votes
1answer
40 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
0
votes
1answer
22 views

Proof verification: (Pretty pictures :) )Showing two graphs are not isomorphic. Bondy/Murty - Graph theory Page 5

I want to show the below two graphs are not isomorphic. Treat the left as graph $\bf G$ and the right as graph $\bf H$. $\bf G$ and $\bf H$ are not isomorhpic: Although we have a bijective mapping ...
0
votes
2answers
21 views

If $G$ is simple, then $\epsilon \leq {v \choose 2}$ - Bondy/Murty - Graph Theory with Applications Page 4

Question: Does this proof hold? Is this a bad proof? Any nicer proofs that don't rely on other theorems? Notation: $\epsilon$ - Number of edges $v$ - Number of vertices G - Here, any Graph ...
0
votes
0answers
23 views

Problems in extremal graph theory [on hold]

Determine ex(n, 2K2) for every n. (Here 2K2 means a pair of vertex-disjoint edges).
-1
votes
0answers
21 views

Graph Theory - Paths

A Θ-graph is a graph consisting of two vertices x and y joined by three paths that share no vertices other than x and y. Prove that any Θ-graph contains an even cycle
0
votes
0answers
18 views

Conjecture: If S = P-1 then (P*(P-1)^S -2)/(P-2) is the least upper bound of N.

Given a point to point computer network where each node has $P$ ports. Let $N$, with optimum wiring, equal the number of nodes can be reached in $S$ transmissions or (skips). Using binomial expansion ...
-4
votes
0answers
35 views

SELF COMPLEMENTARY GRPAHS [on hold]

A simple graph is called self-complementary if it is isomorphic to its own complement. Let G be a simple graph on n vertices. Prove that if G is self-complementary, then either n = 4t or n = 4t + 1 ...
5
votes
1answer
78 views
+50

Number of $K_{10}$ always increases

Let $G=(V,E)$ be a graph with $n\geq 10 $ vertices. Suppose that when we add any extra edge to $G$, the number of complete graph $K_{10}$ in $G$ increases. Show that $|E|\geq 8n-36$. [Source: The ...
0
votes
1answer
25 views

Dimension of cut space

Quoting from Algebraic graph theory by Biggs: If $G$ is a directed graph, then the dimension of cut space is rank of incidence matrix of $G$. Now, my question is: What happens when $G$ is not ...
1
vote
1answer
44 views

Proportion of asymmetric graphs

Wikipedia states, that the proportion $$p(n):=\frac{number\ of \ asymmetric \ graphs \ with\ n\ nodes}{number\ of\ graphs\ with \ n\ nodes}$$ satisfies $$\lim_{n->\infty }p(n)=1$$ I wonder ...
1
vote
0answers
30 views
+50

Partition in graph connecting itself and other half

Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta>10$. Prove that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A|\leq ...
0
votes
2answers
18 views

Is the path between 2 vertices of a Minimum weight tree of a graph the shortest path between those 2 vertices?

Suppose we have an undirected, connected graph, $G_1$ If you have a minimum weight spanning tree $G_2$ for graph $G_1$. Is it possible to find two vertices in $G_1$ which is has a shortest path that ...
0
votes
1answer
20 views

Paths of Nearest Neighbours

I'm working on a project about sampling points, where the next point to be added to sample is the closest point to the current point. Furthermore, each point can only appear once in the sample. ...
-2
votes
0answers
22 views

count minimum spanning tree [closed]

if there is no three edges have the same length in a graph (but two edges can have the same length). How many di efferent MSTs can you have in the worst case? Give an example to show that How fast ...
1
vote
1answer
58 views

Graph of all sets

Working with set theory of ZFC, would it be possible to construct a graph (as in graph theory) with the class of all sets as its nodes? With "is it possible" I mean, would it lead to a contradiction ...
0
votes
0answers
28 views

Spreading a rumour to at least x people with a minimum probability p

I have the following problem: Consider an undirected weighted graph G where the weight of an edge between nodes a and b represents the probability of a message being passed from node a to node b (or ...