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
2answers
168 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
20 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
115 views

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
190 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)
1
vote
1answer
26 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
38 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
35 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 ...
1
vote
1answer
58 views

Find a maximum flow $f$ and a minimum cut $K$ in the network $N$

Find a maximum flow $f$ and a minimum cut $K$ in the network $N$ The book tell me that the max $val(f)=6$ and $K=[X,\overline X]$ with $X=\{u,s\}$. I'm not sure I know how they obtain that result. ...
0
votes
1answer
138 views

Cartesian product of two graphs

How can I show that the number of edges of the Cartesian product of two graphs may be a prime number? Hadwiger number may be useful but I do not know how can I use it
3
votes
2answers
88 views

Graph theory - inequality

I'm having troubles solving the following problem which is about proving an inequality in the field of graph theory. We consider G = (V,E) a graph with n a natural ...
0
votes
2answers
56 views

All non-isomorphic graphs with chromatic number 4

I need to find all non-isomorphic graphs $G=(V,E), |V|=5$ with chromatic number $\chi(G) = 4$. How do I do that?
0
votes
1answer
30 views

Probability of a balanced triangle in graph

I have a complete graph of $n$ nodes. All edges are undirected. Now I mark each sign of edge $e$ positive with probability $p$ and negative with probability $1-p$. I wonder whats the probability ...
0
votes
0answers
42 views

If i Duplicate a graph and connect the new points to the old one the chromatic number stays the same

I want to show χ(H) = χ(G) For every graph við vertices >= 2 (That the chromatic number stays the same after the following) If i take a graph and duplicate it, then connect the new vertex to the old ...
4
votes
2answers
303 views

Number of self-avoiding rook walks in a rectangular grid

I was wondering how many self-avoiding rook walks there are on an $m×n$ grid. A self-avoiding rook walk is a path from the bottom left corner to the top right corner of the grid, composed only of ...
1
vote
2answers
680 views

How to find the largest connected component of an undirected graph using its incidence matrix?

Usually, finding the largest connected component of a graph requires a DFS/BFS over all vertices to find the components, and then selecting the largest one found. Suppose I only have an incidence ...
1
vote
0answers
42 views

Show that no flow can have value exceeding $9$

Let $N$ be the network with source $u$ and sink $v$, where each are is label with its capacity. a) Show that no flow can have value exceeding 9 b) Give an example of a flow $f$ on $N$ such that ...
0
votes
1answer
68 views

Pachner moves for graph of 4-valent nodes

For 3-simplices (i.e. tetrahedra), I understand the basic idea behind the Pachner moves 1 $\leftrightarrow$ 4, which takes one tetrahedron and replaces it with four (or vice versa), and 2 ...
1
vote
0answers
16 views

Graph invariants for rooted trees

I'm looking for a few graph invariants (that have been studied before) that help distinguish rooted trees. I have a large, real-world collection of these graphs and I'd like to see what has been ...
1
vote
0answers
30 views

Automorphism of a 3-connected graph which fixes rooting

I was reading “On the order of the group of a planar map” (Journal of Combinatorial Theory, v1 #3 (1966) pp.394–395) about automorphisms of 3-connected planar graphs. A rooting of a plane graph is a ...
2
votes
1answer
26 views

If $G$ is a graph with diameter $\ge 5$ then $\Delta(G)+\delta(G)\le \left|V(G)\right|-2$

Problem: Let $G$ be a graph with $k$ vertices and diameter $\ge 5$. Why then must the sum of its smallest and greatest degree be smaller or equal to $k-2$? I have tried arguing by induction (assuming ...
0
votes
1answer
107 views

Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
0
votes
2answers
234 views

Increase by one, Shortest path, changes the edges or not? [closed]

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
0
votes
0answers
103 views

Show that the number of isomorphism classes of tree on n vertices is exponentially large as a function on n.

I am currently trying to answer this question: 'Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n−2}}{n!}$ and hence that this is exponentially large as a ...
1
vote
1answer
265 views

Magic Squares with Random Numbers

I'm trying to solve a problem related to Magic Squares. The thing is: Given a list of n numbers, I need to answer if it is possible to create a magic square with them. These numbers are random (no ...
0
votes
1answer
236 views

Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover?

As most of you know, the problem of finding a minimal vertex cover for an arbitrary graph is an NP-hard problem. I was wondering, if there existed a non-constructive way of calculating the size of a ...
0
votes
1answer
74 views

How to justify the statement that a graph is connected?

Is the graph connected? Justify. Because there is a path connecting all pairs of vertices, this graph is therefore connected? Is that right?
0
votes
1answer
48 views

Graph Theory: Discrete Math

I am a student from Iraq studying Graph to get in to a college in Georgia. I have trouble understanding this question. Show that the two definitions below are logically equivalent. Definition 1. A ...
0
votes
1answer
29 views

Polynomial time algorithm to find a 3-connected contracted graph

How can we describe a polynomial-time algorithm to find an edge $e$ in a graph $G$ such that $G/e$ is 3-connected. Given the fact that $G$ is 3-connected and $\lvert V(G) \rvert \geq 5$.
4
votes
1answer
105 views

Choosing subset of vertices connected to whole graph

Consider a simple graph $G$ with $n$ vertices. For any two vertices, either they are connected by an edge, or there is a third vertex which is connected to both of them by an edge. (It is possible ...
0
votes
1answer
98 views

The jelly bean box problem

I believe this is a standard graph theory problem, but I am not sure. I am having a lot of trouble with it though. Give it a go You have n jelly beans. You want to ship them all to a friend. For 1 ≤ ...
0
votes
1answer
78 views

Meaning of “Up to isomorphism”

I saw in my graph theory notes this statement "Up to isomorphism, there is one and only one $K_4$". What does the phrase "up to isomorphism" mean?
1
vote
3answers
122 views

Max length of a path in a connected graph

Let $k$ be the maximum length of a path in a connected graph $G$. If $P, Q$ are paths of length $k$ in $G$, prove that $P$ and $Q$ have a common vertex. My solution: Suppose that $P$ and $Q$ are ...
1
vote
1answer
40 views

Venn Diagram for abritrary set identity

I'm having a bit of a problem with producing a venn diagram of this relationship. I have three circles: $U$, $V$, $W$. The identity I have to create is: $$( U \setminus V ) \setminus W = U \setminus ...
1
vote
1answer
416 views

Number of isomorphism classes of a tree on n vertices

I'm currently trying to solve this problem: "Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n-2}}{n!}$." I'm pretty stumped to be honest. I know of Cayley's ...
0
votes
2answers
104 views

Finding Euler Path without 2 odd degrees?

![image]https://www.dropbox.com/s/o5ybtns0qd7t4b4/s.png?dl=0 Give an example of a Eulerian Path of the graph that starts at A Isn't the graph Eulerian if it has 2 odd number of degrees? when i ...
1
vote
2answers
158 views

Let $G$ be a simple graph. Show that $m\leq {n \choose 2}$, and determine when equality holds.

I'm reading Bondy and Murthy's Graph Theory, and I'm doing the proposed exercise in the title. I've tried to do the following: $m$: Edges $n$: Vertices A simple graph with $n$ vertices has ...
2
votes
3answers
89 views

Proving that there exist 2 distinct vertices $u,v$ in $G$ such that $d(u) = d(v)$

I have difficulties understanding the proof given below showing that there exist 2 distinct vertices $u,v$ in $G$ such that $d(u) = d(v)$ where $G$ is a non-trivial graph. Proof: It's clear that $0 ...
3
votes
1answer
88 views

Is there any graph property which is equivalent to that the spectral radius of its adjacency matrix is less then $1$?

Let $G$ be a directed graph and $A$ the corresponding adjacency matrix. I'll denote with $\rho$ the spectral radius, and with $I$ the identity matrix. What can we say about $G$ when the spectral ...
0
votes
1answer
43 views

clarifiying a definition from graph theory more prcisely definition of A-Bridge

I really don't understand this definition from this paper which is: $A-bridge$: if $A \subseteq V(G)$, then an $A-bridge$ of $G$ is either an edge joining two vertices of $A$ or an edge-maximal ...
2
votes
2answers
3k views

Prove by induction the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).

I'm stuck on this problem, posting my progress so far below. I've looked at similar questions here and here, but neither seem to directly prove the predicate by induction, with a base case followed by ...
9
votes
1answer
204 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
1
vote
1answer
60 views

For a tournament T of order n, let $Δ=max \{od v:v∈V(T)\}$ And $δ=min\{od v:v∈V(T)\}$ Prove that if $Δ-δ< \frac n2$, then T is strong

For a tournament $T$ of order $n$, let $Δ=max \{od v:v∈V(T)\}$ And $δ=min\{od v:v∈V(T)\}$ Prove that if $Δ-δ< \frac n2$, then $T$ is strong Here is my final attemp. Prove this by contrapositive. ...
3
votes
3answers
153 views

Prove the condition of the score sequence make the tournament strong

Prove the theorem 4.19: A non-decreasing sequence $\pi:s_1,s_2,\ldots,s_n$ of nonnegative integers is a score sequence of a strong tournament if and only if $$\sum_{i=1}^ks_i > \binom k 2 $$ for ...
0
votes
1answer
44 views

One set dominating another in tournament

Consider a tournament with $799$ contestants. Each contestant plays against all other contestants exactly one; there are no draws. Prove that there exist two disjoint groups $A,B$, of $7$ contestants ...
2
votes
0answers
84 views

Connected graphs whose complements are connected

The complement of a disconnected graph is necessarily connected, but the converse is not true. For instance, $C_5$ is connected and isomorphic to its complement. The following picture shows a graph ...
1
vote
0answers
49 views

Euclidean Minimum Spanning Tree Property

Is the following statement about Euclidean MSTs true, and if so could someone help me with a proof? Between any two nodes, the EMST minimizes the maximum edge cost of any edge required to traverse ...
1
vote
1answer
94 views

Number of spanning trees for these 2 figures

The solution to the number of spanning trees of the graph below is given by $6$ and $4 \times 4 - 1$ for Graph A and B respectively. I'm not sure how to get this. Please assist. I did ask a similar ...
1
vote
1answer
73 views

Use of model theory in flag algebras

I need to learn about Razborov's "flag algebras" (see http://bit.ly/1u1a1NB) to solve a problem about graphs. Flag algebras are a very general new algebraic tool for studying combinatorial structures. ...
1
vote
1answer
167 views

Number of spanning trees of this graph

The solution to the number of spanning trees of the graph below is given by $3 \times 2 \times 3 = 18$. I'm not sure how to get this. Please assist. Thanks! Notes: Just in case anyone was ...
2
votes
1answer
33 views

confudes with Dijkstra's algorithm.

I have tried to understand the question but I got really confused. So starting from node 3, the distance to other nodes are 3 to 1 = 3 3 to 2 = 1 3 to 4 = 4 3 to 5 = 2 3 to 6 = 3 3 to 7 = 2 ...