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

2
votes
1answer
38 views

Let G be a simple graph with n vertices and m edges. Prove the following holds!!

Let G be a simple graph with n vertices and m edges. Prove the following holds using the Handshake Theorem: $$\frac{m}{\Delta} \leq \frac{n}{2} \leq \frac{m}{\delta}$$ where: $\Delta$ is the maximum ...
0
votes
0answers
22 views

Determine $ex(n,P_k)$ for each pair of n and k

I have to find the maximum number of edges in $P_k$ free graph where $P_k$ is path of length $k$. I know the result that a graph on $n$ vertices with no path of length $k$ has edges$\ \le ...
2
votes
1answer
29 views

Counterexample to a variation on “The politician theorem”.

The following is a theorem in graph theory that has a nice 'real world' interpretation: Suppose $G$ is a finite simple graph in which any two vertices have precisely one common neighbour. Then ...
0
votes
0answers
20 views

graph theory k -coloring proofs, specific problem using countries and neighbors

prove that if any country has at least 5 neighbors, then there are two neighboring countries such that there are not more than 9 other countries adjacent to at least one of these two, each country is ...
1
vote
0answers
23 views

Graph Theory, West, 2nd ed, Exercise 1.2.14

The claim to prove, or disprove is as follows: The union of the edge sets of distinct $u,v$-paths must contain a cycle. The proposed solution is the following: Proof (extremality): Let $P$ ...
4
votes
1answer
32 views

Proposition $1.3$ in Bondy & Murty's Graph Theory.

Let $G[X,Y]$ be a bipartite graph, with no isolated vertices, and $d(x) \ge d(y)$, $\forall$ $xy \in E$ (where $E$ denotes the set of edges in $G$). Then: $|X| \le |Y|$, with equality iff $d(x) = ...
1
vote
2answers
1k views

Solution Verification: Maximum number of edges, given 8 vertices

Suppose a simple graph G has 8 vertices. What is the maximum number of edges that the graph G can have? The formula for this I believe is n(n-1) / 2 where n = number of vertices. 8(8-1) ...
2
votes
1answer
48 views

Friendship theorem: need help with part of proof.

Suppose $G$ is a simple graph such that every two of its vertices have exactly one common neighbor. The friendship theorem says that $G$ must be a friendship graph (a bunch of triangles joined at a ...
2
votes
1answer
49 views

Homology of a graph.

Let $\Gamma$ be a graph with $V$ vertices and $E$ edges. If we orient the edges, we can form the incidence matrix of the graph. This is a $V\times E$ matrix whose $(i j)$ entry is $+1$ if the edge ...
8
votes
4answers
22k views

Proving that the number of vertices of odd degree in any graph G is even

I'm having a bit of a trouble with the below question Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$. ...
0
votes
0answers
24 views

Standard notation for the set of children of a node in a rooted tree

In graph theory, given a rooted tree $T$ and a node $a \in V(T)$, is there a standard way to refer to the set of all children of $a$? I have seen $CHILDREN_T(a)$ being used, but this seem quite clumsy ...
2
votes
0answers
26 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
0
votes
2answers
25 views

$K_n$ as an union of bipartite graphs

Theorem: The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n \leq 2^k.$ I would appreciate a pedagogical explanation of the theorem. Graph Theory by West ...
1
vote
1answer
18 views

Showing an outerplaner graph has less than $2n-3$ edges

An outerplanar graph is a connected plane graph that can be drawn in such a way that all it's vertices are on the outer face. I want to show that for every $G$ outerplaner graph with $n$ vertices and ...
4
votes
2answers
47 views

(A question regarding:) the graph associated with an open cover of a topological space.

Let $X$ denote a topological space and suppose that $\mathcal{O}$ is an open cover of $X$. Assume $\emptyset \notin \mathcal{O}.$ (Thanks Niels!) Now make $\mathcal{O}$ into an (undirected) graph as ...
0
votes
1answer
278 views

Is $G-e$ $(k-1)$-connected?

Prove that if $G$ is a $k$-connected graph and $e$ is an edge of G, then $G-e$ is $(k-1)$-connected. Any hints would be greatly appreciated.
0
votes
0answers
21 views

It is possible to have multiple values in one graph node

Look at the graph: I have this graph and i want to return all possible groups of the graph. Each group is a node, or all the nodes directly below that node. So we can have this type of groups: ...
6
votes
1answer
39 views

$2$-coloring of graph has large connected subgraph with one color

Given a graph $G$ with $n$ vertices. Let $k$ denote the minimum degree among the vertices. Suppose that $k\geq 3n/4$. We color the edges of $G$ in $2$ colors. Prove that there is a connected subgraph ...
1
vote
2answers
35 views

How many edges in a graph with $n$ vertices are needed to guarantee it is connected?

A graph $G$ is connected if every pair of vertices in $u,v\in V$ is connected by some path. For an undirected graph with $n$ vertices, how large does the edge set $E$ have to be to guarantee that it ...
24
votes
0answers
513 views

Is Erdős' lemma on intersection graphs a special case of Yoneda's lemma?

Under which name is the following proposition filed actually: Every poset $P$ embeds fully and faithfully in the powerset of $P$, ordered by subset inclusion. Let me call it Dedekind's lemma. ...
4
votes
2answers
35 views

amenable groups versus amenable graphs

In operator algebras, one is often concerned with amenable groups, defined by one of many equivalent conditions. http://en.wikipedia.org/wiki/Amenable_group#Equivalent_conditions_for_amenability In ...
10
votes
2answers
588 views

In a graph, can an edge be in less than 2 faces?

In the proof that for every conective plane graph on $n$ vertices and $m$ edges $m\leq 3(n-2)$ I encountered the statement: $\Sigma_{f\in F} f\leq 2m$, and the explanation was that every edge is in at ...
1
vote
1answer
30 views

Graph and tree computation

A graph is given with set of nodes $[x_1,x_2,x_3,\ldots,x_6]$ and with set of edges: $$\{[x_1,x_2], [x_1,x_3], [x_1,x_4], [x_1,x_5], [x_1,x_6], [x_2,x_3], [x_2,x_6], [x_3,x_4], [x_4,x_5], ...
2
votes
1answer
465 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
0
votes
0answers
29 views

Degree-Constrained Shortest Path Problem

The following is my problem: Given an undirected graph G(V,E) with cost c(e) associated with every edge e∈E such that c(e)>0 and a vector d=(dv : v∈V) which denotes the maximum degree on each vertex ...
1
vote
1answer
371 views

The number of e-even connected components of a graph

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question: A connected component of a graph is called e-even if the ...
-1
votes
2answers
531 views

what is the maximum number of non-loop edges that can exist in an undirected graph

please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph. for example if vertices are 10 then how many non loop edges can exist?
1
vote
2answers
52 views

Derive formula for number of cables in full-mesh network

I am trying to determine how they derived number of cables needed in a full mesh network According to networking books it is $\dfrac{N * (N-1)}{2}$, where N is the number of nodes. I tried drawing ...
0
votes
0answers
28 views

Graph, Relation $xRy \Leftrightarrow$ There is a path between $x$ and $y$ - symmetry

I have the relation $xRy$ is equivalent to "There is a path between $x$ and $y$" If I now want to check symmetry, $xRy$ is equivalent to $yRx$, I read that this is true. I thought this is only the ...
0
votes
0answers
48 views

Minimum spanning tree for a weighted square grid

I have a particular grid with weighted edges connecting each vertex: From this I'm looking for an easy method to obtain a Minimum Spanning Tree. I can easily check columns or rows and remove all ...
2
votes
1answer
17 views

Reproducing a graph using an incidence matrix

I am very new to graph theory. In fact, I've only begun studying the subject three days ago. So please have mercy if this is a meaningless question! It occurred to me while studying graph ...
2
votes
2answers
78 views

Measuring how “connected” nodes are in a network

I am an undergraduate studying economics and mathematics. I've never studied graph theory formally (only briefly in my spare time) and as such I don't have formal terms for what I'm clumsily trying to ...
18
votes
2answers
878 views

Not lifting your pen on the $n\times n$ grid

Does there exist $n$, and $r<2n-2$, such that the $n\times n$ square grid can be connected with an unbroken path of $r$ straight lines? Note: This has essentially already been asked - see this ...
0
votes
1answer
28 views

Diameter of a graph?

How do you solve this question? The diameter of the graph $C_m$ $\times$ $C_n$ is? Also what does $C_m$ $\times$ $P_n$ mean? (Taking $m \geq 3, n\geq 3$)
3
votes
1answer
70 views

Another Evaluation of the Ramsey number $\mathcal{R}(3,3,3)$

The problem Show that $\mathcal{R}(3,3,3)=17$ The story behind the problem and some notation It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and ...
3
votes
1answer
66 views

Graph Theory text for social scientist.

I am a graduate student in Economics. I have a decent grounding in maths, but I've never studied graph theory or combinatorics. I need to study graph theory in order to analyse production networks. ...
4
votes
0answers
49 views

How to determine if these graphs are isomorphic?

I had this question on my last Discrete exam: (the missing vertex on graph G is vertex d) I did prove that the graphs were isomorphic, but my teacher said that I matched up my vertices wrong. ...
4
votes
1answer
226 views

Prove the connected components are uncountably many

Let $G$ a graph with vertices all the points in $\mathbb{R}^2$. An edge exists if and only if the distance between two points is a rational number. Prove that the connected components are ...
1
vote
2answers
48 views

Nauty software package and weighted graphs

I am working with software package Nauty. It there a way to add weighted graphs in nauty software package?
1
vote
1answer
35 views

Lower bound for the size of a maximal matching in a general graph

Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximal matching, and let $M^\star\subseteq E(G)$ be a maximum matching. Prove that $|M|\ge |M^\star|/2$. Any hints on how to prove this?
0
votes
0answers
16 views

Extract and search an unweighted multigraph from an undirected weighted graph?

I have an undirected weighted graph G(V,E) where the nodes are bus stops and the edges are the distances between the stops. I've implemented a basic Dijkstra to search the shortest path (s, t) which ...
-1
votes
1answer
41 views

the sum of numbers at any row and at any column of this matrix is exactly 1.

All entries of an n × n matrix are non-negative. It is known that the sum of numbers at any row and at any column of this matrix is exactly 1. Prove that you can choose n positive entries such that ...
0
votes
1answer
15 views

Name of a graph that shows various strengths

I am looking for the name of a graph used to show various strengths. It is a polygon and may look like this: _ | | | | | * | _ Where the ...
0
votes
0answers
33 views

Looking to get a handle on SSCG(3) (which is much, much larger than TREE(3))

TREE numbers grow rapidly: TREE(1) = 1, TREE(2) = 3, and a lower bound for TREE(3) is A(A(...A(1)...)), where the number of As is A(187196) and A(n) is a version of Ackerman's function. That's ...
1
vote
2answers
31 views

Path and cycle length proof

How can we prove this proposition : Every graph G contains a path of length $ \delta(G)$ and a cycle of length at least $ \delta(G) + 1$, provided that $\delta(G) \geq 2 $. ($ \delta(G)$ is the ...
1
vote
1answer
35 views

help with graph theory question

Let $A_1A_2A_3A_4$ be a square, and let $A_5,A_6,A_7,\ldots,A_{34}$ be distinct points inside the square. Non-intersecting segments $\overline{A_iA_j}$ are drawn for various pairs $(i,j)$ with $1\le ...
1
vote
1answer
134 views

How to prove it's possible to place $8$ non-attacking rooks on a chessboard with $7$ cells cut out?

From the 8 × 8 chessboard 7 cells were cut out. Prove that you can put 8 rooks to this board so that none of them can capture another rook.
2
votes
1answer
26 views

Graph Theory-Eulerian Path?

In a certain country, $40$ roads lead out of each city. When all roads are open, it is possible to travel from any city to any other. Each road leads from one city to another; there are no dead end ...
0
votes
1answer
39 views

sitting around a table- graph theory?

$50$ mathematicians attend a conference at which each knows $25$ other attendees. Show that you can select $4$ of them who can then be seated at a round table, such that each person at the table knows ...
5
votes
1answer
462 views

The number of paths on a graph of a fixed length w/o repeatings

Sorry for bad English. Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$. But what if we can't walk through a vertex ...