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

Graph diameter and average pairwise distance

How do I prove that for a graph G, I can always find a constant c>0 such that $$ \frac{diameter(G)}{average \ pairwise \ distance (G)} > c $$ where $$ average \ pairwise \ distance = ...
2
votes
2answers
19 views

In any finite graph with at least two vertices, there must be two vertices with the same degree

Show that, in any finite graph with at least two vertices, there must be two vertices with the same degree. HINTS ONLY!
2
votes
1answer
42 views

Graph theory/pigeonhole question.

In a waiting room, there are 100 people, each of whom knows 67 others among the 100. Prove that there exist 4 people in the waiting room who all know each other (that is, each know the other 3). You ...
0
votes
0answers
44 views

Graph with minimum degree $\ge 3$ and exact $1$ hamilton circuit

Enumerating the graphs upto $9$ vertices and the cubic connected graphs upto $18$ vertices, I did not find a graph with minimum degree $\ge 3$ and exact $1$ hamilton circuit. Is there a graph with ...
0
votes
1answer
15 views

Upper bound on chromatic number characterization with longest directed path

"Show that $\chi (G)\leq k$ if and only if $G$ admits an orientation such that the longest path has length at most $k-1$." The greedy algorithm may be helpful for proving one direction of the ...
0
votes
1answer
42 views

how to prove that $\alpha(C_5 \boxtimes C_5)=5$?

how to prove that $\alpha(C_5 \boxtimes C_5)=5$? $C_5$ is cycle of length 5 and $\boxtimes$ is strong product of graphs http://en.wikipedia.org/wiki/Strong_product_of_graphs $\alpha$ is the maximum ...
0
votes
1answer
8 views

Bounds on the eigenvalues of an undirected graph with a least one edge

Question Consider an undirected, unweighed, graph $G$ with no self loops with at least one edge. Let the eigenvalues of the adjacency matrix $A(G)$ be denoted by $\lambda_i$, I would like to show ...
4
votes
0answers
40 views

Probabilistic counting inequality

I am reading a proof involving the existence of a property in a tournament (a directed complete graph). To make the proof work, we need to have $n^ke^{-n/2^k}<1$. Here $n$ is the order of the ...
0
votes
1answer
16 views

Which operations create a minor of a graph?

I came across two definitions which operations are allowed to construct a minor from a given graph. One definition allows edge contractions and edge deletions, the other additionally vertex ...
4
votes
1answer
166 views

Graph Min Cut Problem

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ...
0
votes
1answer
19 views

How can I show complete graphs are determined by spectrum?

I understand how to prove a complete graph $K_n$ has spectrum $\lbrace -1^{(n-1)},n-1 \rbrace$. However I am having difficulty proving that the spectrum uniquely determines the complete graph. ...
0
votes
2answers
42 views

What is the girth and circumference of 4-dimensional cube?

What is the girth and circumference of Q4 (4-dimensional cube, a graph on 16 vertices),how can I prove it? Girth means the length of a shortest cycle,and circumference means the length of a longest ...
1
vote
1answer
43 views

$3$-connected graph isomorphism problem

If $G$ is $3$-connected, then $G$ contains a subgraph isomorphic to $H$, where $H$ is obtained from $K_4$ by replacing the edges of $K_4$ by internally disjoint paths. Any hints and proofs are ...
0
votes
1answer
39 views

Seating at a Dinner Party

At a dinner party, there are $2n$ guests to be seated at a round table. Each guest knows $n$ of the other guests. Show that it is possible to seat the guests so that each is between two acquaintances. ...
1
vote
1answer
16 views

Show that if $T$ is a spanning tree of $G$ that is distance preserving from some vertex of $G$, then $diam(G) \leq diam(T) \leq 2diam(G)$

Let $G$ be a connected graph. a) Show that if $T$ is a spanning tree of $G$ that is distance preserving from some vertex of $G$, then $diam(G) \leq diam(T) \leq 2diam(G)$ b) show that for every ...
0
votes
0answers
24 views

Exactly one minimum spanning tree

A all edges in a graph of n vertices have differing weights. How can I prove that there is exactly one minimum spanning tree?
1
vote
1answer
25 views

$2$-connected graphs with a line graph containing no hamilton cycle

Let G be a simple undirected graph. I found some examples of connected graphs G with line graphs containing no hamilton cycle, but none of them was $2$-connected. Are there $2$-connected graphs ...
1
vote
0answers
31 views

Correct process for proof in graph theory.

I'm working on what I'm sure is a fairly basic proof in graph theory. I must prove that $Every$ $graph$ $G$ $contains$ $a$ $path$ $with$ $\delta(G)$ $edges$. $\delta(G)$ is the minimum degree of the ...
0
votes
2answers
37 views

The effect on k(G) of removing a vertex or an edge

Consider an (a, b) graph G (ie a graph with a vertices and b edges). Let k (G), the minimum amount of vertices that can be removed to disconnect the graph, be n>=1. What would be the possible effects ...
1
vote
1answer
49 views

$k$-connected graphs containing trees

I've encountered the following problem in the book "Graphs and Digraphs" and I'm not sure how to do it. Show that every $k$-connected graph contains any tree of order $k+1$ as a subgraph.
0
votes
0answers
26 views

possible values of vertex/edge connectivity after removal of one vertex/edge (Graph Theory)

Suppose G is a (p,q) graph (p vertices, q edges) with k(G)=n k_1(G)=m (where k(G) and K_1(G) are vertex connectivity and edge connectivity respectively), such that m,n>=1. What values are possible for ...
0
votes
0answers
44 views

Graph Theory proof regarding edge connectivity

I can't seem to figure out this proof. Any help would be greatly appreciated! Prove that if G is a graph of order p and minimum degree of G (d(G)) >= p/2, then the edge connectivity of G (k_1(G))= ...
3
votes
1answer
31 views

Automorphism groups of vertex transitive graphs

Does there exist a finite nonoriented graph whose automorphism group is transitive but not generously transitive (that is, it is not true that each pair $(x,y)$ of vertices can be interchanged by some ...
0
votes
1answer
20 views

Graph Theory inequality

I've been trying to prove the following inequality If G is r-regular graph and $\kappa (G)=1 $, then $\lambda (G)\leq \left \lfloor \frac{r}{2} \right \rfloor$ I've tried manipulating the Whitney ...
0
votes
0answers
10 views

Labelling graph over an abelian group

I was reading about this equivalence of labellings on a graph where they mentioned about a group equivalence as a product of an automorphism with a labelling. I don't understand what kind of product ...
0
votes
0answers
13 views

Trees and Leaves (Graph Theory)

Let $T$ be a tree with $l$ leaves and $k \in \mathbb{Z}^{+}$ with $2k \geq l$. I need to show that there exists paths $P_{1}, P_{2},...,P_{k}$ such that: (i) $P_{1} \cup P_{2} \cup ... \cup P_{k} = ...
0
votes
0answers
23 views

How to find and prove the girth and circumference of the petersen graph

How to find and prove the girth and circumference of the Petersen graph? Does any one could help me? Thanks.
1
vote
3answers
41 views

Coloring simple graph

Given a graph with $5$ vertices and $6$ edges. Find the chromatic number and polynomial. The chromatic number is trivial, it would of course be $3$. But I am completely clueless on how to find the ...
0
votes
1answer
38 views

How to know if a graph exists or not?

Draw the required graph or explain why no such graph exists: 8-vertex, 2 component, simple graph with exactly 10 edges and three cycles. I think there is a graph but I'm not sure. Can anyone help to ...
0
votes
0answers
21 views

Criticise work with simple graphs & problem solving

So I'm studying graph theory at the moment and would like some constructive criticism or thoughts on my method. The problem can be formulated as follows. I'm looking for someone to verify my answer as ...
1
vote
1answer
13 views

Formal way of counting vertices

For a simple graph $G = (V,E)$ we know that there are $10$ edges, $|E|=10$. And we know that two vertices have a degree of $4$, and the rest have a degree of $3$. I know how to solve this, I'm just ...
1
vote
0answers
19 views

breaking a graph into two by removing 4 edges

Consider a simple planar 4-valent graph. I want to find out how to break it into two pieces by removing 4 edges, if such a way exists. Removing the four edges belonging to a single vertex doesn't ...
0
votes
0answers
23 views

Minimum Degree of a Graph

A graph $G = (V,E)$ satisfies $| E | <= 3 | V | - 6$. The min-degree of $G$ is defined as $\min \{\deg (v)\}$. Therefore, min-degree of G cannot be __ I don't know how to approach this problem . ...
0
votes
0answers
13 views

Dividing graph into branches

I would like to know an algorithm to produce a graph decomposition into branches with rank in the following way: ...
3
votes
1answer
20 views

Question about the proof that 'A graph with maximum degree at most k is (k + 1) colorable

I'm trying to follow the MIT introductory mathematics for cs course. In the reading on graph theory, the proof that a graph with maximum degree at most k is (k + 1) colorable is given as follows: ...
2
votes
0answers
56 views

Classification of maximally non-hamiltonian graphs?

A graph is called maximally non-hamiltonian, if it does not contain a hamilton-cycle, but no edge can be added without creating a hamilton-cycle. In other words, every pair of non-adjacent vertices ...
1
vote
1answer
73 views

Expected size of the connected component containing a randomly selected node

Given an Erdős–Rényi random graph with n nodes and edge probability p, what is the expected number of nodes in the connected component containing a randomly selected node? In other words, if I ...
2
votes
1answer
30 views

eigenfunctions on covering spaces of graphs

I am reading about lifts of graphs in relation to covering spaces. Before I pose my question I will explain some of the terminology. Let $G$ and $H$ be two graphs. We say that a function $f: V(H) ...
0
votes
0answers
15 views

Euler path line graphs and their duals?

Am having trouble drawing a dual of a given graph, I have tried it but I don'tvthink am correct. How should this question be done, below is also my trial;
1
vote
2answers
32 views

Is there a relationship between the clique of a graph and colouring of a graph?

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the ...
0
votes
1answer
30 views

Resolving circular references in probability-graph

(Apologies, if the title is not accurate/useful, I'm not sure what else to call it... Ideas welcome...) Let's say I have a game that consists of several states S1, S2, S3, ... and coin-tosses that ...
3
votes
1answer
25 views

Let $T$ be a tree of order $n$.Show that $T$ is isomorphic to a subgraph of $\overline{C}_{n+2}$

Let $T$ be a tree of order $n$.Show that $T$ is isomorphic to a subgraph of $\overline{C}_{n+2}$ I'm allowed to use this theorem: for every tree $T$ of order $k$. If $G$ is a graph such that ...
1
vote
1answer
26 views

Let $G$ be a connected graph that is not a tree. Let $u,v \in V(G)$ such that $G-u$ and $G-v$ are both tree. Show that $deg(u)=deg(v)$

Let $G$ be a connected graph that is not a tree. Let $u,v \in V(G)$ , $u \not =v$ such that $G-u$ and $G-v$ are both tree. Show that $deg(u)=deg(v)$ Here is what I got so far. Let $T_1 =G-u$ and ...
2
votes
0answers
25 views

Is there a layer of abstraction on top of the graph?

Not sure if this is the most answerable question, but it is worth a shot. I am slowly getting into math, and have been interested in graph theory for a while. I use it in programming all the time. ...
2
votes
0answers
24 views

Generalization of Kneser's graph

Let's consider subsets of the set $\{1,\dots,n\}$ which consist of $m$ elements. I wonder, what is the maximal number of such subsets such that cardinality of intersection of any two of them isn't ...
0
votes
1answer
75 views

What proves clustering preserves DAG property?

English is not my first language so sorry for beeing unable to explain the situation as exactly as I would like to. I try to proof that if i got serial processes clustered, clusters are always ...
0
votes
2answers
30 views

In a Complete graph, prove $ \sum n_{i} = n, then { n_{i} \choose 2 } \le { n \choose 2 } $

I'm studying graphs in algorithm and complexity, but I'm not very good at math. In a Complete graph, prove $ \sum n_{i} = n, then { n_{i} \choose 2 } \le { n \choose 2 } $ ? please give some ideas.
1
vote
2answers
35 views

In complete graph, how can I prove ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$

I'm studying graphs in algorithm and complexity, but I'm not very good at math. How can I prove that ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$?
-1
votes
0answers
25 views

Cycle in 2 randon picks from k subset in s k-connect graph

Can you help me with this exercise ? Prove that a graph $G$ of order $n \geq k+1\geq 3$ is $k$-connected if and only if for each set $S$ of $k$ distinct vertices of $G$ and for each two-vertex ...
0
votes
0answers
53 views

Show that for every two vertices $u$ and $v$ of $3$-connected graph $G$, there exists two internally disjoint $u-v$ paths of different lengths in $G$

Can you help me with this exercise? I have no idea how to resolve it. A) Show that for every two vertices $u$ and $v$ of $3$-connected graph $G$, there exists two internally disjoint $u-v$ paths of ...