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

Characterizations of operation that take a path and produce a star in a tree

I was looking at this operation in a tree, and try to relate it to the diameter of the tree. Pick a path of length $m$, so let it be $v_1v_2\ldots v_mv_{m+1}$. Remove all the edges in the path, and ...
1
vote
1answer
158 views

Question on the number of directed edges in a tournament.

I want to show that there exists $c>0$ constant s.t for any tournament on $n$ vertices there are two disjoint subsets A and B s.t: $$ e(A,B)-e(B,A) \geq c n^{\frac{3}{2}}$$ I know of the theorem ...
1
vote
0answers
205 views

A tree that does not satisfy: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$?

It is a strange question on a book. Give an example of a tree $T$ that does not satisfy the following property: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$. I ...
2
votes
1answer
103 views

Minimal Weighted Graph Paths?

Suppose we have a connected undirected graph with a positive integer cost assigned to each edge. Given two verticies, how do we find the set of minimal cost paths between those two nodes? Does this ...
6
votes
1answer
3k views

How to prove that a simple graph having 11 or more vertices or its complement is not planar?

It is an exercise on a book again.If a simple graph G has 11 or more vertices,then either G or is complement $\bar { G } $ is not planar. How to begin with this?Induction? Thanks for your help!
3
votes
1answer
440 views

Matching in a random graph

Hi can anyone help me? nothing I tried worked so far We build the following random graph: G=(L∪R,E) be a bipartite random graph when |L|=|R|=n. Each vertex v∈L chooses randomly and independently with ...
4
votes
3answers
2k views

How to determine the number of directed/undirected graphs?

I'm kind of stuck on this homework problem, could anyone give me a springboard for it? If we have $n\in\mathbb{Z}^+$, and we let the set of vertices $V$ be a set of size $n$, how can we determine the ...
4
votes
1answer
268 views

Spectral graph theory and connected components of graphs

We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem? How do we know that this works in ...
3
votes
1answer
968 views

Is a 2-regular graph the same as a single cycle?

When I was doing some graph theory problem, came to my mind this corollary: Graph G is a single cycle if and only if $\displaystyle \forall_{v\in V[G]}\deg(v)=2$ I don't know whether I make ...
2
votes
2answers
121 views

Cycle in Graph with $Δ(G)\leq 10$

I have a graph named $G$. degree of each node in $G$ is at most $10$. I need to find an algorithm to determine that this graph has any cycle with length less than $20$ with $O(n)$ . I think it can ...
1
vote
1answer
442 views

Consensus in Discrete-Time and Matrix Theory [closed]

I have an $N \times N$ adjacency matrix $A_{ij}$ for nodes $i$ and $j$, numbered 1 through $N$. Each node $i$ starts with a scalar value $x_i(0)$ between 0 and 1. At each non-negative integral time ...
6
votes
2answers
4k views

Expected value of number of edges of a connected graph

There are n vertices. 2 vertices are chosen such that there is no edge between them and add an edge between them. We choose each pair with equal probability. Once we a have a completely connected ...
1
vote
1answer
476 views

Finding planar representation of graph

If it is known that a graph is planar, how do we find a planar representation of the graph? Is there any method other than trial and error? Thanks a lot.
0
votes
2answers
366 views

Subdivisions of graphs (must the vertices be distinct)

By Kuratowski's Theorem, A graph is planar if and only if it does not contain a subgraph isomorphic to a subdivision of K5 or K(3,3). My question is that for the subdivision of K5 (or K(3,3) formed ...
4
votes
1answer
583 views

Sum of the shortest paths in graph

Let $ d_{G} \left(x,y \right) $ be the length of the shortest path between the vertices $x$ and $y$ in graph $G$ and let $s\left(G\right) = \sum_{x,y \in V \left[G\right]} d_{G} \left(x,y \right)$ . ...
0
votes
3answers
688 views

Party problem / Ramsey's theorem R(3,3)

I'm looking for an algorithm that solve Party problem. The party problem asks to find the minimum number of guests that must be invited so that at least 3 will know each other or at least 3 will not ...
18
votes
2answers
493 views

Groups and generating sets

This question feels completely trivial and I am somewhat embarrassed to be asking it, but I am having a brain dead moment and failing to prove what I'm sure is a completely trivial statement about ...
3
votes
2answers
1k views

A graph with degrees 0 2 2 4 4 4?

Given a graph with 6 vertices of degrees 0 2 2 4 4 4, in what ways may it be drawn? Simple and connected or some combination of? Obviously it can't be connected due to the vertex with degree 0, but ...
5
votes
1answer
335 views

Graph with 10 nodes and 26 edges must have at least 5 triangles

This is not a homework question, but I would appreciate if people would treat this as if it were homework. I am looking for (nonspoiler) hints. I would like to prove that given any graph with 10 ...
1
vote
2answers
739 views

Find all the non-isomorphic graphs whose degree sequence is $(6,3,3,3,3,3,3)$

Sorry I'm new here, can someone please help me out with this question. I missed a couple of lectures and I don't even know where to start. I'm trying to find all the non-isomorphic graphs whose degree ...
0
votes
1answer
196 views

Shortest path with rotation costs.

There are dotes on the plane $(x,y)$ connected with directed edges. The distance $\rho(A,B)$ is standard euclidean: $|\overrightarrow{AB}|$. Except the distance cost we pay for rotation: $k\alpha$, ...
4
votes
3answers
329 views

If a graph of $2n$ vertices contains a Hamiltonian cycle, then can we reach every other vertex in $n$ steps?

Problem: Given a graph $G,$ with $2n$ vertices and at least one triangle. Is it possible to show that you can reach every other vertex in $n$ steps if $G$ contains a Hamilton cycle (HC)? EDIT: ...
3
votes
1answer
300 views

Algorithm to Find All Vital Edges in a Minimum Weight Spanning Tree

I am trying to locate an algorithm that can find ALL vital edges (edges whose deletion strictly increases the cost of the minimum weight spanning tree in the resulting graph) in a minimum weight ...
0
votes
2answers
1k views

Graph theory bipartite proofs with induction

I have this question I am given in a quiz and right away I did not even do it...I absolutely suck at induction as well as any kind of proofs. This question unfortunately had both...No matter what ...
1
vote
3answers
1k views

Graph with cycles proof questions

Two questions I'm stuck with: If C is a cycle, and e is an edge connecting two nonadjacent nodes of C, then we call e a chord of C. Prove that if every node of a graph G has degree at least 3, then ...
1
vote
1answer
41 views

Getting the formula of a live counter

I'm looking to replicate this greenhouse gases counter in my website. Poking around i found the initial data for the formula. The counter use the following information: Beginnig date: 2012/03/01 ...
1
vote
0answers
1k views

Dijkstra's Algorithm on a Directed Graph with Negative Edges Only Leaving the Source

I've been trying to figure out if Dijkstra's algorithm will always succeed on a directed graph that can have edges with negative weights leaving the source vertex only (all other edges are positive), ...
2
votes
0answers
770 views

Minimum Spanning Tree in a Complete Graph

We generate a complete euclidean graph by taking N random points from a limited (1.0 x 1.0 square) 2D space, connecting them all together (complete graph) and giving the edges weights proportional (or ...
13
votes
3answers
834 views

Counterexamples to proofs of correct statements

This question is in part inspired by a quote I saw in an answer to another question: The problem with incorrect proofs to correct statements is that it is hard to come up with a counterexample. ...
1
vote
1answer
346 views

Paths in a full graph

Given a complete graph with $4$ nodes, and one node is labeled $X$, find how many paths of length $N$ (might visit a node more than once) begin, end or both begin and end with $X$. This is not a ...
1
vote
0answers
56 views

Adding metric to matroids in order to describe graphs whose vertices are points in Euclidean space

My concern is about finding a mathematical model in order to describe graphs as combinatorial structures (with operations like edge addition, deletion and so on), and as elements in the Euclidean ...
1
vote
3answers
104 views

Matchings Containing Given Edges

Version 1 Is there a connected graph containing edges $e_1, e_2, e_3$ such that there is a perfect matching containing any two of the edges but no perfect matching containing all three? EDIT: ...
5
votes
5answers
8k views

Given a simple graph and its complement, prove that either of them is always connected.

I was tasked to prove that when given 2 graphs $G$ and $\bar{G}$ (complement), at least one of them is a always a connected graph. Well, I always post my attempt at solution, but here I'm totally ...
1
vote
4answers
4k views

A finite graph with exactly two vertices with odd degree must have a path joining them.

I would really appreciate it if anyone would validate if my argument ( proof ? ) for the above statement is valid. I am aware of other proofs but the current argument is more of a task in ...
1
vote
1answer
222 views

Graph Theory Confusion

What is the most number of regions (including the outside region) can a planar graph with V vertexes partition split the plane into? (No self-loops or multiedges allowed) Im stumped on this question ...
2
votes
0answers
72 views

Directed infinite 1-pseudo-trees

I'm looking for any literature or results on infinite directed 1-pseudo-trees. Brief definitions: A pseudo-tree is a tree with at most once cycle. 1-pseudo-trees have outdegree of exactly 1 ...
1
vote
1answer
100 views

Left or right edge in cubic planar graph

Given a cubic planar graph, if I "walk" on one edge to get to a vertex, it it possible to know which of the other two edges is the left edge and which one is the right edge? Am I forced to draw the ...
0
votes
1answer
402 views

Maximal number of bridges for a given vertex count and minimal degree

For the problem statement below, what would be best way to prove it? I have a solution which I think is not very elegant which is why I am asking this question: Prove that no graph on 100 vertices ...
3
votes
5answers
6k views

Graph Theory - How can I calculate the number of vertices and edges, if given this example

An algorithm book Algorithm Design Manual has given an description: Consider a graph that represents the street map of Manhattan in New York City. Every junction of two streets will be a vertex of ...
1
vote
0answers
63 views

A non-distinct system of representative edges.

I have the following problem: Let $ \mathcal{G} = \{ G_i \}_{i=1 \ldots n} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_i ...
2
votes
1answer
98 views

Statements Equivalent to a Graph Being Eulerian

Theorem: Let G be a connected graph, then the following are equivalent (i) each vertex of G has even degree (ii)G has some cycles which between them use each edge of G once and only once (iii) G ...
1
vote
3answers
1k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...
0
votes
1answer
310 views

Getting an instance of a cycle in a directed graph

(I asked the same question in stackoverflow, but thought that this website might be the another good place to ask this.) I want an algorithm that gives one instance of a cycle in a directed graph if ...
1
vote
4answers
1k views

How to find all proper colorings (four coloring) of a graph with a brute force algorithm

I'd like to implement a brute force algorithm to search ALL the different colorings of a map. In terms of graph theory I'd like to find all four colorings of the vertices of a planar graph (the dual ...
1
vote
1answer
895 views

simple graph theory cycle problem

Looking for some hint on a question in an assignment "Find a graph which has some vertices u, v and w such that there is a cycle containing both u and v, a cycle containing both v and w, but no cycle ...
5
votes
4answers
2k views

what are the applications of the isomorphic graphs?

While studying data structures i was told my instructor that even i am given 3 hour/30 days/3 years to find out whether two graphs are isomorphic or not, it is very very complex and even after ...
0
votes
1answer
272 views

Max flow Min cut Problem

I have this problem in my Question paper for the BE exam I appeared. I am not able to understand the problem statement and dont know how to use max flow min cut theorem to use it. Please guide me ...
7
votes
3answers
1k views

Significance of eigenvalue

When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
0
votes
1answer
442 views

Graphs with diameter equal to two times the radius

In basic graph theory books, we learn that the radius (rad) and diameter (diam) satisfy $$rad(G) \leq diam(G) \leq 2 rad(G)$$ I have seen books talk about graphs for which $rad(G) = diam(G)$. These ...
25
votes
1answer
9k views

Is Sage on the same level as Mathematica or Matlab for graph theory and graph visualization?

The context: I'm going to start working on a project that involves running predefined algorithms (and defining my own) for very big graphs (thousands of nodes). Visualization would also be welcome if ...