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

6
votes
3answers
333 views

Secret Santa Perfect Loop problem

(n) people put their name in a hat. Each person picks a name out of the hat to buy a gift for. If a person picks out themselves they put the name back into the hat. If the last person can only ...
1
vote
1answer
72 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
1answer
41 views

P - bounded polyhedron, L - linear map. Show that L(P) is a bounded polyhedron

Let $P = \{x\in \mathbb{R}^n \ | \ Ax\leq b\}$ be a bounded polyhedron. Let $L:\mathbb{R}^n \rightarrow \mathbb{R}^k$ be a linear map. Show that $L(P):=\{L(x)\ | \ x\in P\}$ is a bounded polyhedron. ...
0
votes
1answer
58 views

Is this a Red-Black Tree?

I tried to build RBT (Red-Black Tree) via this way: I build a balanced binary search tree (much as I can) and then colored it... Now the Q is: if this is a legal RBT? At my opinion is yes, because ...
4
votes
1answer
75 views

Graph with only the identity as endomorphism

Is there a graph $G$ with more than one vertex such that the identity $\textrm{id}: G\to G$ is the only graph homomorphism from $G$ to itself? Is there even an infinite example?
1
vote
1answer
34 views

Show that $\delta(G) \geq 4$ if $\chi(G)=5$ and $\chi(G-v) =4$ for each vertex $v \in G$

Let G be a graph satisfying the following conditions: (1) $\chi(G)=5$ and (2) $\chi(G-v) =4$ for each vertex $v \in G$ Show that $\delta(G) \geq 4$. Answer given: Suppose $\delta(G) \leq 3.$ Let ...
1
vote
1answer
35 views

Maximum number of highways

There are 20 cities in a country, some of which have highways connecting them. Each highways goes from one city to another, both ways. There is no way to start in a city, drive along the highways of ...
0
votes
1answer
43 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
1
vote
1answer
259 views

Number of possible graphs from a reachability matrix?

I need to know how to work out how many possible different digraphs can be drawn from a given reachability matrix. It needs to be with the minimum number of arcs between the nodes within the graph ...
1
vote
1answer
82 views

Power set ordered by sum and Dijkstra shortest path

I've needed to enumerate the power set ordered by the sum of elements in each subset. Luckily I've found a nice solution here: Algorithm wanted: Enumerate all subsets of a set in order of increasing ...
0
votes
1answer
40 views

Number of graphs with M edges that does not contain K-clique

If we consider the space of graphs $G(n,M)$ with $n$ vertices and $M$ denotes the number of edges. Is there any way of upper bounding the number of graphs in this space that does not contain any ...
0
votes
1answer
37 views

Proof between max independent set cardinal and min vertex cover.

i'm tryign to solve this problem for my graph class, but I don't really know where to start. Be G a graph without isolated vertex,proof that it verifies that $\alpha \leq \beta$, where $\alpha$ is ...
0
votes
1answer
12 views

Clarification on Eulirian cycle proof

I have trouble in understanding this proof can some one clarify the following elements: (1)Why does it follow that if T has maximum length, then $v_0=v_k$?(2)What does E represent?(3)What does E(T) ...
1
vote
0answers
56 views

Example of a k-matroid

Let the set $K_i = (S, I_i)$ be a matroid for each $i \in \{1 \ldots k\}$. We define $K = (S, I) $ where $I = \{ X \subset S $ | $ X \in \bigcap_{i=1}^k I_i\}$ The claim now is that $K$ is a ...
1
vote
1answer
1k views

Minimum number of edges to ensure connectedness

Question: Consider a simple graph G with n vertices. What is the minimum number of edges that G must have in order to ensure that it is connected? Justify your answer. My attempt: Let G = $(V, E)$. ...
0
votes
1answer
40 views

given a point cloud of n points, create a convex shape that defines their outer limits

I have a point cloud. I find its 'centre' by averaging the coordinates of each point. I translate the cloud so the average is at the origin (for simplicity sake) I want to then create a convex shape ...
1
vote
1answer
129 views

What is the multiplicity of the largest eigenvalue of a graph?

The Laplacian of a graph is a symmetric positive semi-definite matrix and hence has all real eigenvalues. Is there any characterization for the multiplicity of the largest Laplacian (and/or Adjacency ...
1
vote
1answer
44 views

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not .

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not . if we consider $0=\mu_1 \leq \mu_2 \leq ...\leq \mu_n$ as the eigenvalue of laplacian matrix ,we ...
0
votes
1answer
55 views

Coloring edges of $K_n$ so each vertex has $l$ edges of each color.

Given $n$ for what values of $l$ can we color the edges so that each vertex $l$ edges of each color adjacent to it. The number of colors used is clearly $\frac{n-1}{l}$ Thank you in advance.
2
votes
2answers
124 views

Is the product of (modified) adjacency matrices of two matchings necessarily symmetric?

Consider $n$ vertices, and two (not necessarily perfect) matchings $M_1$ and $M_2$. With the following definition of a (modified) adjacency matrix of a matching, can we claim that $A(M_1)\cdot A(M_2)$ ...
0
votes
2answers
45 views

Assign integers to the vertices of $G$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less ...
1
vote
1answer
732 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
3
votes
1answer
80 views

Does a colouring of a graph on two colours always have certain kinda of circle

Is there a planar set of points $P$ $(|P|\geq 4)$ such that no matter how you colour the points with two colours you can always find four points on a circle so that all four of the point have the ...
2
votes
2answers
148 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

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 ...
1
vote
1answer
16 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
32 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 ...
0
votes
1answer
29 views

Finding nodes with a particular weight in a graph

Given a weighted graph $G=(V,E)$ and given two integers $n$ and $k$, I want to find (if they exist) $n$ nodes such that the sum $S$ of all the edges incident to such $n$ nodes is smaller than $k$. Of ...
0
votes
1answer
45 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
1answer
160 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
108 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
31 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 = ...
2
votes
1answer
48 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 ...
2
votes
0answers
49 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
36 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 ...
2
votes
1answer
58 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
1answer
234 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
1answer
166 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 ...
0
votes
0answers
52 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
90 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
32 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
28 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
65 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
25 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
1answer
51 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 ...
1
vote
0answers
25 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
68 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
111 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
1answer
177 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
284 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
356 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 ...